알고리즘 - 빙고 python

🎈 착안점

빙고인 케이스를 세가지로 나눴다.
1. 가로 빙고
2. 세로 빙고
3. 대각선 빙고

1, 2 케이스는 쉽게 코드로 구현할 수 있을 거라 생각했는데, 3번인 대각선 케이스를 처음엔 어떻게 구현해야할지 떠오르지 않았다. 그런데 잘 생각해보면 대각선으로 빙고를 할 수 있는 경우는 단 두가지다(왼쪽 사선으로, 오른쪽 사선으로).

초기 코드(일부)

def solution(board, nums):
    N = len(board)
    result = 0
    
	# 가로 탐색
    for i in range(N):
        count = 0
        for j in range(N):
            if board[i][j] not in nums:
              break
            count += 1
            if count == N:
                result += 1
                
	# 세로 탐색
    for i in range(N):
        count = 0
        for j in range(N):
            if board[j][i] not in nums:
                break
            count += 1
            if count == N:
                result += 1

💥 문제점

• 이런식으로 코드를 짰을 때(생략했지만 대각선 케이스도 존재), 정확도는 모두 통과했지만, 효율성에서 모조리 실패했다.
• 이중 for문을 썼으니 당연한 결과라고 생각했지만, 원인은 사실 list에 in 혹은 not in을 사용하여 시간복잡도가 O(n)이 나온 것이었다. 결국 나는 3중 for문을 만든 꼴이었으니 시간 에러가 나오는 게 당연했다.
  +완전 탐색을 위해 이중 for문은 필요한 요소라고 한다
• 즉, list에 not in을 쓰는 대신, 해시를 사용하여 시간복잡도를 O(1)로 줄이는 방법을 사용해야 한다.
• defaultdict를 이용하여 nums를 해시로 만들었다.

💛 수정 후 코드

from collections import defaultdict
def solution(board, nums):
    N = len(board)
    result = 0
    
    # dictionary 생성
    hash_nums = defaultdict(int)
    for num in nums:
        hash_nums[num] += 1
        
    # 가로 탐색
    for i in range(N):
        count = 0
        for j in range(N):
            if hash_nums[board[i][j]] != 1:
                break
            count += 1
            if count == N:
                result += 1
                
    # 세로 탐색
    for i in range(N):
        count = 0
        for j in range(N):
            if hash_nums[board[j][i]] != 1:
                break
            count += 1
            if count == N:
                result += 1

    # 오른쪽 아래 대각선
    count = 0
    for i in range(len(board)):
        if hash_nums[board[i][i]] != 1:
            break
        count += 1
        if count == N:
            result += 1

    # 왼쪽 아래 대각선
    count = 0
    for i in range(len(board)):
        if hash_nums[board[i][(len(board)-1) - i]] != 1:
            break
        count += 1
        if count == N:
            result += 1

    return result

🎈 추가

hash_nums라는 dictation 자료형을 선언했는데, 위 문제에선 nums의 갯수가 1을 넘는 경우가 없으니 dictation의 모든 value값은 1이 된다. 이런 경우는 set()을 선언하는것이 더 좋다.

무엇보다 set()은 list와 달리, 순서를 지킬 필요가 없는 자료형이다. 때문에 set과 관련된 메서드는 O(1)인 경우가 많기 때문에 효율성 문제에서도 효과적이다.

ex)
if i in list( ): O(n)
if i in set( ): O(1)