백준 2578번 빙고 Python 풀이

🕵️‍♂️ 문제 탐색

문제 설명:
사회자가 부르는 숫자에 따라 빙고판의 숫자를 지우면서, 빙고(한 줄이 모두 지워진 경우)가 3줄 이상 완성되었을 때 사회자가 몇 번째 숫자를 부른 후 빙고가 완성되는지 구하는 문제이다.

 

시간복잡도 분석:

1. 숫자 탐색 및 갱신:
   • 각 숫자를 탐색하고 해당 위치를 지우는 데는 O(1) (해시맵 활용).
   • 따라서, 총 25개의 숫자를 갱신하는 데 O(25) = O(1).
2. 빙고 체크:
   • 빙고를 매번 확인하는 데 O(5+5+2)=O(12) (5개의 행, 5개의 열, 2개의 대각선 빙고 체크).
   • 숫자 25개를 부를 동안 매번 확인하므로 최종 복잡도는 O(25×12)=O(300). 결국, O(1)

결론적으로, 입력 크기가 작아 O(300)으로 끝날 수 있다.

 

적합한 알고리즘:

1. 빙고판 초기화:
   • 빙고판의 숫자와 위치를 관리하기 위해 해시맵을 생성
2. 사회자 숫자 처리:
   • 숫자를 부를 때마다 해당 숫자를 빙고판에서 제거
3. 빙고 체크:
   • 행, 열, 대각선에서 5개의 숫자가 모두 제거되었는지 확인
4. 빙고 완성 시점 출력:
   • 빙고가 3줄 이상 완성되는 첫 번째 순간의 숫자 순서를 출력

---

🛠️ 코드 설계

1️⃣ 입력 처리 및 초기화

• 빙고판의 숫자와 위치를 해시맵으로 저장
• 사회자가 부르는 숫자 리스트를 저장

2️⃣ 숫자 처리 및 빙고 체크

• 숫자를 부를 때마다 해시맵에서 해당 위치를 찾고 체크 배열을 갱신
• 각 행, 열, 대각선을 확인하여 빙고의 개수를 계산

3️⃣ 결과 출력

• 빙고가 3줄 이상 완성된 순간의 순서를 출력

---

💻 정답 코드

def bingo():
    board = [list(map(int, input().split())) for _ in range(5)]  # 빙고판 입력
    numbers = [int(x) for _ in range(5) for x in input().split()]  # 부르는 숫자 입력

    position = {board[i][j]: (i, j) for i in range(5) for j in range(5)}

    row_check = [0] * 5
    col_check = [0] * 5
    diag_check = [0] * 2  # 대각선 체크

    for count, number in enumerate(numbers, start=1):
        if number not in position:
            continue  # 숫자가 빙고판에 없으면 무시
        x, y = position[number]  # 숫자의 위치 찾기

        row_check[x] += 1
        col_check[y] += 1
        if x == y:  # 왼쪽 위에서 오른쪽 아래 대각선
            diag_check[0] += 1
        if x + y == 4:  # 오른쪽 위에서 왼쪽 아래 대각선
            diag_check[1] += 1

        bingo_count = row_check.count(5) + col_check.count(5) + diag_check.count(5)
        if bingo_count >= 3:  # 빙고가 3줄 이상 완성되면 종료
            print(count)
            return

bingo()