선밥의 공부하는 블로그

혼자서 하는 틱택토

문제 링크

혼자서 하는 틱택토

분석

2차원 배열인 board가 3x3크기로 주어집니다.
해당 배열은 "0", "x", "."으로 이루어져 있습니다.

틱택토 게임을 올바르게 진행했을 경우 매개변수로 주어진 board가 나올 수 있는 지 판별하고, 반환하는 문제입니다.

주요 조건은 다음과 같습니다.

  • "0"가 항상 먼저 시작합니다.
  • "0"의 수는 항상 "X"와 같거나 많습니다.
  • "0"와 "X"의 개수 차이는 최대 1개이어야 합니다.
  • "0"나 "X"가 가로, 세로, 대각선으로 같은 문자가 3개 연속 배치되어야 승리입니다.
  • "0"나 "X"가 승리했다면 누군가 추가로 돌을 둘 수 없으며, 게임은 즉시 끝나야합니다.

풀이

#include <string>
#include <vector>

using namespace std;

// 보드에서 특정 플레이어가 승리했는지 확인하는 함수
bool checkWin(const vector<string>& board, char player)
{
    // 가로 확인
    for (int i = 0; i < board.size(); ++i)
    {
        if (board[i][0] == player && board[i][1] == player && board[i][2] == player)
        {
            return true;
        }
    }
    
    // 세로 확인
    for (int j = 0; j < board[0].length(); ++j)
    {
        if (board[0][j] == player && board[1][j] == player && board[2][j] == player)
        {
            return true;
        }
    }
    
    // 대각선 확인
    if (board[0][0] == player && board[1][1] == player && board[2][2] == player)
    {
        return true;
    }
    else if (board[0][2] == player && board[1][1] == player && board[2][0] == player)
    {
        return true;
    }
    
    // 승리하지 못한 경우임
    return false;
}

int solution(vector<string> board) {
    // O와 X의 개수를 센다.
    int oCount = 0;
    int xCount = 0;
    
    for (int i = 0; i < board.size(); ++i)
    {
        for (int j = 0; j < board[0].length(); ++j)
        {
            if (board[i][j] == 'O')
            {
                ++oCount;
            }
            else if (board[i][j] == 'X')
            {
                ++xCount;
            }
        }
    }
    
    // X가 O 개수보다 많거나 O가 X보다 2개 이상 많다면 규칙에 위반된다.
    if (xCount > oCount || oCount > xCount + 1)
    {
        return 0;
    }
    
    // O와 X가 승리했는지 확인하고 저장한다.
    bool isOWin = checkWin(board, 'O');
    bool isXWin = checkWin(board, 'X');
    
    // 둘 다 승리한 경우 규칙에 위반된다.
    if (isOWin && isXWin)
    {
        return 0;
    }
    // O가 승리했지만 X와 개수가 같다면 규칙에 위반된다.
    else if (isOWin && oCount == xCount)
    {
        return 0;
    }
    // X가 승리했지만 O와 개수가 다르다면 규칙에 위반된다.
    else if (isXWin && oCount != xCount)
    {
        return 0;
    }
    
    // 위반된 규칙이 없는 경우 
    return 1;
}

성능 요약

시간 복잡도는 $O(1)$의 시간 복잡도를 가집니다.

  • board의 크기는 3x3으로 고정되어 있으므로 $O(1)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.01ms, 4.22MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.29MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.15MB)
테스트 7 〉 통과 (0.01ms, 4.14MB)
테스트 8 〉 통과 (0.01ms, 4.13MB)
테스트 9 〉 통과 (0.01ms, 4.43MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 4.14MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.21MB)
테스트 14 〉 통과 (0.01ms, 4.16MB)
테스트 15 〉 통과 (0.01ms, 4.22MB)
테스트 16 〉 통과 (0.01ms, 4.2MB)
테스트 17 〉 통과 (0.01ms, 4.21MB)
테스트 18 〉 통과 (0.01ms, 3.68MB)
테스트 19 〉 통과 (0.01ms, 4.21MB)
테스트 20 〉 통과 (0.01ms, 4.21MB)
테스트 21 〉 통과 (0.01ms, 4.21MB)
테스트 22 〉 통과 (0.01ms, 4.21MB)
테스트 23 〉 통과 (0.01ms, 4.28MB)
테스트 24 〉 통과 (0.01ms, 4.2MB)
테스트 25 〉 통과 (0.01ms, 3.68MB)
테스트 26 〉 통과 (0.01ms, 4.21MB)
테스트 27 〉 통과 (0.01ms, 3.59MB)
테스트 28 〉 통과 (0.01ms, 4.21MB)
테스트 29 〉 통과 (0.01ms, 4.2MB)
테스트 30 〉 통과 (0.01ms, 4.21MB)
테스트 31 〉 통과 (0.01ms, 4.21MB)
테스트 32 〉 통과 (0.01ms, 4.44MB)
테스트 33 〉 통과 (0.01ms, 4.19MB)
테스트 34 〉 통과 (0.01ms, 4.02MB)
테스트 35 〉 통과 (0.01ms, 4.02MB)
테스트 36 〉 통과 (0.01ms, 4.16MB)
테스트 37 〉 통과 (0.01ms, 4.14MB)
테스트 38 〉 통과 (0.01ms, 4.18MB)
테스트 39 〉 통과 (0.01ms, 4.21MB)
테스트 40 〉 통과 (0.01ms, 4.14MB)
테스트 41 〉 통과 (0.01ms, 4.14MB)
테스트 42 〉 통과 (0.01ms, 4.14MB)
테스트 43 〉 통과 (0.01ms, 4.21MB)
테스트 44 〉 통과 (0.01ms, 3.68MB)
테스트 45 〉 통과 (0.01ms, 4.2MB)
테스트 46 〉 통과 (0.01ms, 4.2MB)
테스트 47 〉 통과 (0.01ms, 4.14MB)
테스트 48 〉 통과 (0.01ms, 4.43MB)
테스트 49 〉 통과 (0.01ms, 4.22MB)
테스트 50 〉 통과 (0.01ms, 4.21MB)
테스트 51 〉 통과 (0.01ms, 4.22MB)
테스트 52 〉 통과 (0.01ms, 3.65MB)
테스트 53 〉 통과 (0.02ms, 3.63MB)
테스트 54 〉 통과 (0.01ms, 3.68MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글