[백준 2578번] 빙고 - python

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

📌 문제 탐색하기

목표

• 빙고 게임 만들어서 선이 세 개 이상 그어지게 만드는 수 출력하기
• 빙고는 가로, 세로, 대각선을 취급한다.

입력값

• 첫 줄부터 총 다섯 줄까지 빙고판에 써질 숫자가 주어진다. 1~25까지의 수가 하나씩 입력된다.
• 사회자가 부르는 수가 여섯째 줄부터 열째 줄까지 주어진다. 마찬가지로 1~25까지의 수가 하나씩 입력된다.
  • ex)
  • 11 12 2 24 10 16 1 13 3 25 6 20 5 21 17 19 4 8 14 9 22 15 7 23 18 5 10 7 16 2 4 22 8 17 13 3 18 1 6 25 12 19 23 14 21 11 24 9 20 15

출력값

• 철수가 “빙고”를 외치게 되는 숫자를 출력한다. 빙고는 가로, 세로, 대각선 중 3개 이상의 선이 그어져야지 외칠 수 있다.
  • ex)
  • 15

📌 코드 설계하기

해결 아이디어

• 시간 복잡도는 1초이지만 빙고판이 매우 작다. for문을 두 번돌아도 25번의 연산이라 크게 시간 복잡도를 고려하지 않아도 될 것이라고 생각했다.
• 빙고판을 만들고 각 수를 모두 받고 난 후에 시작하기로 했다.
• 주어진 수가 빙고판에 존재하면 해당 위치의 수를 0으로 초기화한다.
• 입력이 주어질 때 마다 가로, 세로, 대각선을 훑으며 모두 0인 줄이 있는지 확인한다.
• 해당 줄이 있으면 check를 1씩 높여서 check가 3 이상일 때 exit()한다.

📌 정답 코드

import sys

zero = [0, 0, 0, 0, 0]
def find (arr, num):
    for i in range (5):
        for j in range(5):
            if arr[i][j] == num:
                arr[i][j] = 0
                return
            
def column_zero (arr, check):
    for j in range(5):
        if [i[j] for i in arr] == zero:
            
            check += 1
    return check

def row_zero(arr, check):
    for i in range(5):
        if arr[i] == zero:
            check +=1 
    return check

def dia(arr, check):
    num = 0
    for i in range(5):
        if arr[i][i] == 0:
            num += 1
    if num == 5:
        check +=1
    num = 0
    for i in range(5):
        if arr[i][4-i] == 0:
            num +=1
    if num == 5:
        check +=1 

    return check
                
bingo = []
numbers = []
for i in range (5):
    bingo.append(list(map(int, sys.stdin.readline().split())))

for i in range(5):
    numbers.append(list(map(int, sys.stdin.readline().split())))

for i in range (5):
    for j in range(5):
        check = 0
        find(bingo, numbers[i][j])
        check = column_zero(bingo, check)
        check = row_zero(bingo, check)
        check = dia(bingo, check)
        
        if check >= 3:
        
            print(5 * i + j+1)
            exit()

시간 복잡도 계산해보기

• 입력 처리
  • bingo.append(list(map(int, sys.stdin.readline().split()))) * n → O($N^2$)
  • numbers.append(list(map(int, sys.stdin.readline().split()))) * n → O($N^2$)
  • 합치면 → O($N^2$)
• for문
  • 이중 for문 → O($N^2$)
  • find(), column_zero(), row_zero(), dia()
    • 이중 for문 → O($N^2$)
  • dia()
    • 대각선 2개 * 각 O(N) → O(N)
  • 출력 처리
    • 계산 후 출력 → O(1)
  • 합치면 → $O(N^4)$

최종 시간 복잡도: $O(N^4)$