[프로그래머스 코딩테스트]Level03 - 빙고

Level 03 - 빙고

문제 설명

빙고는 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이하의 자연수이며, 중복된 수가 들어있지 않습니다.
  

입출력 예

|—|—|—| |board |nums |result| |[[11,13,15,16],[12,1,4,3],[10,2,7,8],[5,14,6,9]]|[14,3,2,4,13,1,16,11,5,15]|3| |[[6,15,17,14,23],[5,12,16,13,25],[21,4,2,1,22],[10,20,3,18,8],[11,9,19,24,7]]|[15,7,2,25,9,16,12,18,5,4,10,13,20]|2|

첫번째 시도-실패

정확성 테스트는 다 통과하지만, 효율성 테스트에서 시간초과 뜸.

# 시간초과됨!!
def solution(board, nums):
    # 최대 빙고 수: 보드 크기 n*n일 때 2*n(가로세로) + 2(대각선)
    answer = 0
    n = len(board)
    row_0_cnt = 0
    col_0_cnt = 0
    diag_0_cnt1 = 0
    diag_0_cnt2 = 0

    for i in range(n):
        for j in range(n):
            if board[i][j] in nums:
                board[i][j] = 0
                row_0_cnt += 1
        if row_0_cnt == n:
            answer += 1
        row_0_cnt = 0
    # print(board)
    
    for i in range(n):
        for j in range(n):
            if board[j][i] == 0:
                col_0_cnt += 1
            if i==j and board[i][j] == 0:
                diag_0_cnt1 += 1
            if i+j==n-1 and board[i][j] == 0:
                diag_0_cnt2 += 1

        if col_0_cnt == n:
            answer += 1

        col_0_cnt = 0

    # print(col_0_cnt)
    # print(row_0_cnt)
    # print(diag_0_cnt1)
    # print(diag_0_cnt2)
    if diag_0_cnt1 == n:
        answer += 1
    if diag_0_cnt2 == n:
        answer += 1

    return answer

print(solution([[11,13,15,16],[12,1,4,3],[10,2,7,8],[5,14,6,9]], [14,3,2,4,13,1,16,11,5,15])) # 3

단순하게 리스트로 하나씩 체크하다보면 시간 초과가 발생한다.
n이 빙고판의 크기라 했을 때 O(n^2 * nums) 만큼 시간이 걸리게 된다.
따라서 입력 값인 nums를 Hash로 만들어 O(1)로 체크하는 방식으로 구현해야 함!

• 해시(Hash)란?
  • 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것
  • 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array 이다
  • 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이때 사용하는 함수(알고리즘)를 해시함수 라고 한다
  • 해시값 자체를 index로 사용하기 때문에 평군 시간복잡도가 O(1) 로 매우 빠르다

두번째 시도-성공

def solution(board, nums):
    # 최대 빙고 수: 보드 크기 n*n일 때 2*n(가로세로) + 2(대각선)
    answer = 0
    n = len(board)

    # dict.fromkeys(키리스트)는 키 리스트로 딕셔너리를 생성
    # nums 리스트 값을 키로 하여 dictionary로 만든다.
    nums = dict.fromkeys(nums)
    row = [0]*n # board 행의 길이
    col = [0]*n # board 열의 길이
    left_diag = 0 # 왼쪽대각선
    right_diag = 0 # 오른쪽대각선

    for i in range(n):
        for j in range(n):
            if board[i][j] in nums: 
                # 해당 숫자가 위치한 행과 열을 체크한다.
                row[i] += 1
                col[j] += 1
                if i==j: # (0,0), (1,1), ... 왼쪽대각선
                    left_diag += 1
                if i+j==n-1: # i+j == n-1은 좌표 몇개 찍어서 계산하면 금방 나옴. 오른쪽대각선
                    right_diag += 1
        
    for i in row: # 행마다 체크된 숫자의 개수가 n이면 빙고
        if i==n:answer+=1
    for j in col: # 열마다 체크된 숫자의 개수가 n이면 빙고
        if j==n:answer+=1
    if left_diag==n:answer+=1 # 왼쪽 대각선 체크된 숫자의 개수가 n이면 빙고
    if right_diag==n:answer+=1 # 오른쪽 대각선 체크된 숫자의 개수가 n이면 빙고

    return answer

print(solution([[11,13,15,16],[12,1,4,3],[10,2,7,8],[5,14,6,9]], [14,3,2,4,13,1,16,11,5,15])) # 3