[파이썬/python] 백준 - 2578 빙고

문제

https://www.acmicpc.net/problem/2578

---

문제 설명

1.   5*5 크기의 빙고 판이 입력으로 주어진다.
   1.   숫자는 1~25사이로 중복없이 입력된다.
2. 사회자가 부르는 숫자 25개가 순서대로 입력된다.
3. 몇 번째 숫자를 불렀을 때 빙고가 완성되는지 검증한다. 
   1. 참고로 3빙고 뿐만 아니라 그 이상의 빙고가 나와도 완성으로 판단한다. 

 

---

풀이

1. 빙고판 배열의 가로, 세로, 대각선 조합을 딕셔너리의 키, 밸류로 매핑한다.
2. 사회자가 부르는 숫자를 1개씩 확인하며, 딕셔너리의 키를 순회하며 부른 숫자가 키에 존재하면 카운트를 증가시킨다.
   1. 카운트가 5가되면 빙고가 완성된다. 최종 빙고의 개수를 1 증가시킨다.
   2. 최종 빙고의 개수가 3개 이상이라면 함수를 종료하고 결과를 출력한다.

---

코드

import sys
input = sys.stdin.readline

board = [tuple(map(int,input().split())) for _ in range(5)]
answer = [tuple(map(int,input().split())) for _ in range(5)]
dic = {}

for i in range(5):
    dic[(board[i])] = 0

for i in range(5):
    tmp = []
    for j in range(5):
        tmp.append(board[j][i])
    dic[tuple(tmp)] = 0

tmp = []
for i in range(5):
    tmp.append(board[i][i])
dic[tuple(tmp)] = 0
dic[(board[4][0],board[3][1],board[2][2],board[1][3],board[0][4])] = 0
cnt = 0

for i in range(5):
    for j in range(5):
        n = answer[i][j]
        for k,v in dic.items():
            if n in k:
                if dic[k] == 4:
                    dic[k] = 5
                    cnt += 1
                dic[k] += 1
        if cnt > 2:
            print(i*5 + j+1)
            exit()

---

시간복잡도

• 최악의 경우 25번째 숫자에서 빙고가 완성된다고 가정하자.(그럴일은 없지만)
• 25 * 12(가로,세로,대각선의 개수) * 5(한 줄의 크기) = 약 O(1500)의 시간복잡도가 소요된다.