[Python] 빙고
문제 설명
빙고는 NxN 크기의 게임 보드 칸에 1부터 NxN까지의 자연수를 중복 없이 하나씩 적은 후 숫자를 하나씩 지워나가는 게임입니다. 이때, 가로, 세로, 대각선 방향으로 한 줄에 적힌 숫자를 모두 지울 경우 빙고를 1개 만들었다고 합니다. 다음은 4X4 크기의 게임 보드를 이용해 게임을 진행한 예시입니다.
위와 같이 각 칸에 숫자가 적혀 있을 때, 위 게임 보드에서 순서대로 지운 숫자가 [14,3,2,4,13,1,16,11,5,15]인 경우 아래와 같이 빙고 3개가 만들어집니다.
빙고 게임 보드에 적힌 숫자가 담겨있는 배열 board, 게임 보드에서 순서대로 지운 숫자가 들어있는 배열 nums가 매개변수로 주어질 때, board에서 nums에 들어있는 숫자를 모두 지우면 몇 개의 빙고가 만들어지는지 return하도록 solution함수를 완성해주세요.
제한사항
- board는 게임 보드 칸에 적힌 숫자를 뜻하는 NxN크기의 2차원 배열이며, N은 2 이상 500이하의 자연수입니다.
- board의 각 칸에는 1 이상 NxN이하의 자연수가 중복 없이 하나씩 들어있습니다.
- nums는 board에서 지울 숫자가 들어있는 배열이며, 길이는 1 이상 NxN이하입니다.
- nums에 들어있는 숫자는 1 이상 NxN이하의 자연수이며, 중복된 수가 들어있지 않습니다.
입출력 예
입출력 예 설명
입출력 예 #1 문제의 예시와 같습니다.
입출력 예 #2 다음 그림과 같이 2개의 빙고가 만들어집니다.
풀이
빙고가 될 수 있는 경우는 가로줄, 세로줄, 대각선 3가지입니다.
1) 가로줄과 세로줄 빙고를 세기 위해 col_sum 과 row_sum 리스트를 만듭니다. board의 모든 칸을 돌면서, nums안에 포함된다면 해당 행과 열 인덱스에 1을 더해줍니다
ex) 만약 (2,3) 원소가 nums에 있다면 col_sum의 3번째 값에 1을 더하고, row_sum의 2번째 값에 1을 더해줍니다.
각 원소의 값이 board의 행과 일치한다면 빙고가 완성되었다는 뜻입니다.
ex) board가 4X4 이고, col_sum이 [4,4,2,2]라면 1번째 열과 2번째열이 빙고 달성
이때, nums안에 포함되는지 확인하는 작업이 반복적이기 때문에 list대신 set안에 담아줍니다.
in의 시간복잡도가 list에서는 O(N)이지만 set에서는 O(1)입니다.
2) 대각선의 경우 왼쪽 상단에서 오른쪽 하단으로 가는 대각선(diag_sum1)과 오른쪽 상단에서 왼쪽 하단으로 가는 대각선(diag_sum2)이 있습니다.
diag_sum1은 row 와 col이 같은 지점을 확인해서 nums안에 포함된다면 1씩 더해주고 총합이 board의 행이라면 빙고가 완성되었다는 뜻입니다.
diag_sum2는 row + col 이 len(board) + 1 인 경우를 확인하면 됩니다.
빙고가 완성되는 경우들을 모두 합하여 answer를 출력합니다.
def solution(board, nums):
answer = 0
N = len(board)
set_nums = set(nums)
col_sum = [0 for _ in range(N)]
row_sum = [0 for _ in range(N)]
diag_sum1 = 0
diag_sum2 = 0
for row in range(len(board)):
for col in range(len(board)):
if board[row][col] in set_nums:
col_sum[col] += 1
row_sum[row] += 1
if (row == col) and board[row][col] in set_nums:
diag_sum1 += 1
if (row + col == N-1) and board[row][col] in set_nums:
diag_sum2 += 1
answer += len([x for x in col_sum if x == N])
answer += len([x for x in row_sum if x == N])
answer += diag_sum1 == N
answer += diag_sum2 == N
return answer
