[Python] 프로그래머스 Lv 3 - 빙고

아싸 빙고!

프로그래머스 Lv 3 빙고 풀이

 

알고리즘

처음에는, 일단 빙고판을 하나 또 깡으로 복사해서 0으로 모두 채우고, 리스트에 하나씩 있나 검사를 한다음
열이 모두 채워졌나, 행이 모두 채워졌나, 대각선은 되나 이렇게 각각을 검사했다.

어떻게던 풀겠지만 당연히 효율성에서 실패!

따라서 애초에 행과 열, 대각선을 입력 시점에서 모두 검사해야 한다. 이에 따라 행별로 숫자를 기록할때마다 1을 더할 리스트, 열도 1개 만들고, 대각선은 각 방향별로 변수를 미리 만들어둔다.

board의 각 칸에 있는 값이 nums에 있는지 검사하면 된다.

근데, 이마저도 그냥 board in nums 를 하는 순간 효율성을 또 통과하지 못한다.

효율성을 위해 nums를 val값 없이, 키 값만 존재해도 dict를 만들어 탐색의 효율성을 올리면 통과된다.

  

풀이

def solution(board, nums):
    answer = 0
    size = len(board)
    # 딕트를 강제로 만들어서 접근을 빠르게 해버린다.
    nums = dict.fromkeys(nums)
    
    row_list = [0 for _ in range(size)]
    col_list = [0 for _ in range(size)]
    diag_1 = 0
    diag_2 = 0
    
    # 원소를 넣을 때마다 좌표를 돌려버린다.
    for i in range(size):
        for j in range(size):
            if board[i][j] in nums:
                row_list[i] += 1
                col_list[j] += 1
                if i == j:
                    diag_1 += 1
                if size - i - 1 == j:
                    diag_2 += 1
    if diag_1 == size:
        answer += 1
    if diag_2 == size:
        answer += 1
    answer += sum([1 for i in row_list if i == size])
    answer += sum([1 for j in col_list if j == size])
    return answer