혼자서 하는 틱택토(프로그래머스) 문제풀이

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/160585

프로그래머스

 

 

문제 접근 방식

보드가 주어졌을 때, 해당 보드가 규칙을 어겼는지 판별하는 문제이다. 여러 접근 방법이 있겠지만 실수가 발생하는 상황을 우선 파악 후, 나머지 상황을 정상적인 상황으로 판단하는 방향으로 문제를 풀었다. 아래 3가지 경우에 해당한다면 실수가 발생했다고 판단한다.

 

1. [O의 개수 - X의 개수 = 0 or 1] 이 아닌 경우

O의 개수와 X의 개수를 통해 보드에 이상이 있는지 파악할 수 있다. O의 개수는 X의 개수와 같거나 또는 1이 커야 정상이기 때문에 그 외 경우가 주어진다면 실수가 발생했다고 판단한다.

 

2. O 연속 개수가 1개인데, X의 개수가 O의 개수 이상인 경우

O 연속 개수가 1개이면, O가 표시를 하고 바로 종료되는 상황이다. 선공에서 공격이 끝났기 때문에 후공은 공격을 하지 못하기 때문에 선공의 개수가 1개 많아야한다. 즉, X의 개수가 O개수보다 같거나 많은 경우라면 실수가 발생한 것이다.

 

3. X 연속 개수가 1개 인데, O와 X의 개수가 같지 않은 경우

X의 연속 개수가 1개라면 후공에서 공격이 끝난 것이다. 선공과 후공의 공격 횟수가 같아야하며 그렇지 않은 경우라면 실수가 발생한 것이다.

 

이렇게 3가지에 해당하는 경우 실수가 났다고 판정할 수 있다. 해당 접근 방식으로 풀기 위해 연속된 O,X 를 구하는 count_sequence 라는 함수를 구현하여 문제를 풀었다.

 

 

시간 복잡도

3X3 의 보드를 이중 for 문을 통해 순회하기 때문에 상수시간이 걸린다.

 

코드

# 보드에서 연속된 O,X 개수를 구한다.
# 입력 : board
# 출력 : [연속한 O의 개수, 연속한 X의 개수]
def count_sequence(board): 
    o_sequence, x_sequence=0,0
    for i in range(3):
        # 가로
        if board[i]=='OOO':
            o_sequence+=1
        elif board[i]=='XXX':
            x_sequence+=1
        # 세로
        if board[0][i] =='O' and board[1][i]=='O' and board[2][i]=='O':
            o_sequence+=1
        elif board[0][i] =='X' and board[1][i]=='X' and board[2][i]=='X':
            x_sequence+=1
    
    # 대각선 좌측상단 -> 우측하단
    if board[0][0] =='O' and board[1][1]=='O' and board[2][2]=='O':
        o_sequence+=1
    elif board[0][0] =='X' and board[1][1]=='X' and board[2][2]=='X':
        x_sequence+=1
    
    # 대각선 우측상단 -> 좌측 하단
    if board[0][2] =='O' and board[1][1]=='O' and board[2][0]=='O':
        o_sequence+=1
    elif board[0][2] =='X' and board[1][1]=='X' and board[2][0]=='X':
        x_sequence+=1
    
    return [o_sequence,x_sequence]


def solution(board):
    o_count,x_count=0,0
    
    # board의 O,X 개수 구하기
    for i in range(3):
        for j in range(3):
            if board[i][j]=='O':
                o_count+=1
            elif board[i][j]=='X':
                x_count+=1
    # [O 개수 - X 개수 = 0 or 1] 이 아닌 경우
    if not (o_count==x_count or o_count==x_count+1):
        return 0
    
    o_sequence, x_sequence=count_sequence(board)
    answer = 1
    
    # 틀리는 조건에 해당한다면 answer=0 으로 변경
    if o_sequence==1 and o_count<=x_count:
        answer=0
    elif x_sequence==1 and o_count!=x_count:
        answer=0
    
    
    return answer

 

 

회고

코드가 너무 조잡한 것 같아서 다른 사람의 풀이를 보니 파이썬의 라이브러리를 사용하여 간단하게 표현한 것을 볼 수 있었다.

# all 함수 & for문을 사용하여 모든 값이 'O' 인지를 확인
for i in range(3):
    if all(cell == player for cell in board[i]):
        return True
        
# 대각선
if all(board[i][i] == player for i in range(3)):
    return True
    
# O의 개수 구하는 부분
num_o = sum(row.count('O') for row in board)