[파이썬/Python] 백준 2578번: 빙고

숨·2024년 7월 1일

알고리즘 문제 풀이

목록 보기

11/105

📌 문제 : 백준 2578번

📌 문제 탐색하기

✅ 입력 조건
1. 5번 반복해서 5개의 숫자를 공백으로 구분해 입력
2. 그다음 5번 반복하여 사회자가 부른 숫자를 5개씩 공백 구분해 입력
3. 25개의 숫자는 1~25의 수가 한 번씩 사용
✅ 출력 조건
1. 빙고가 되는 사회자의 마지막 수가 몇 번째인지 출력

빙고의 조건
1. 가로줄, 세로줄, 대각선 위의 5개의 모든 수가 지워지면 선 긋기
2. 선이 3개 이상 그어지면 "빙고"

25개의 수 중에서 사회자가 부른 수를 하나씩 0으로(= 방문 처리) 바꿔준다.
사회자의 수는 빙고판 형식으로 저장하지 않아도 되니까 리스트에 추가하는 식으로 입력받는다.

빙고 함수로 4개 경우의 줄 긋는 상황을 체크한다.
1. 가로
2. 세로
3. 왼쪽 위 → 오른쪽 아래 대각선 (줄 긋는 경우 1개만 나옴)
4. 오른쪽 위 → 왼쪽 아래 대각선 (줄 긋는 경우 1개만 나옴)
이것이 3회 이상이면 해당 숫자의 순서를 출력한다.

가능한 시간복잡도

25개 입력받기 → $O(25) = O(1)$
이중 for문으로 빙고 0으로 바꾸기 → $O(25) = O(1)$
4개의 함수로 빙고 체크 → $O(4*25) = O(1)$

최종 시간복잡도
$O(1)$ 로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

25개의 숫자를 for문으로 체크하면서 빙고 확인하기.

📌 코드 설계하기

빙고 함수 구현
철수 : 5번 반복해 한 줄에 5개 숫자 입력
사회자 : 5번 반복해 한 줄에 5개 숫자 입력
철수, 사회자의 숫자 비교
빙고이면 해당 숫자의 순서 출력

📌 시도 회차 수정 사항

1회차

빙고가 되는 최소 개수가 12개라는 것을 활용해 사회자가 부른 숫자가 12번째 이상일 때만 빙고 체크 함수가 동작하도록 변경하였다. 조건을 잘못 작성했는지 고치기 전보다 결과 %가 낮을 때 틀렸다고 나왔다.

order = k + 1
if order >= 12:
    line = 0
    line += check_horizontal()
    line += check_vertical()
    line += check_diagonal1()
    line += check_diagonal2()

2회차

count = 0
# 4. 철수, 사회자의 숫자 비교
for k in range(25):
    check_num = numbers[k]

    # 4-1. 부른 숫자 0으로 변경
    for i in range(5):
        for j in range(5):
            if bingo[i][j] == check_num:
                bingo[i][j] = 0
                count += 1

    # 4-2. 빙고 체크
    if count >= 12:
        line = 0
        line += check_horizontal()
        line += check_vertical()
        line += check_diagonal1()
        line += check_diagonal2()

        # 5. 빙고이면 해당 숫자의 순서 출력
        if line >= 3:
            print(k + 1)
            break

따로 count하도록 변경해보았는데 효과는 없었다.

3회차

# 1-2. 세로
def check_vertical():
    line = 0
    for i in range(5):
        count = 0
        for j in range(5):
        	#### 조건을 가로 체크 함수와 동일하게 작성...
            if bingo[j][i] == 0:
                count += 1
        if count == 5:
            line += 1
    return line

조건을 넣는 것이 정답이 아니라, 애초에 세로를 체크하는 함수가 틀렸다. 세로 체크 함수는 인덱스를 가로의 반대로 작성해야 했는데 조건을 똑같이 작성했다.

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. 빙고 함수 구현
# 1-1. 가로
def check_horizontal():
    line = 0
    for i in range(5):
        count = 0
        for j in range(5):
            if bingo[i][j] == 0:
                count += 1
        if count == 5:
            line += 1
    return line

# 1-2. 세로
def check_vertical():
    line = 0
    for i in range(5):
        count = 0
        for j in range(5):
            if bingo[j][i] == 0:
                count += 1
        if count == 5:
            line += 1
    return line

# 1-3. 왼-오 대각선
def check_diagonal1():
    count = 0
    for i in range(5):
        if bingo[i][i] == 0:
            count += 1
    if count == 5:
        return 1
    return 0

# 1-4. 오-왼 대각선
def check_diagonal2():
    count = 0
    for i in range(5):
        if bingo[i][4-i] == 0:
            count += 1
    if count == 5:
        return 1
    return 0

# 2. 철수 : 5번 반복해 한 줄에 5개 숫자 입력
bingo = [list(map(int, input().split())) for _ in range(5)]

# 3. 사회자 : 5번 반복해 한 줄에 5개 숫자를 리스트에 추가
numbers = []
for k in range(5):
    numbers.extend(list(map(int, input().split())))

# 4. 철수, 사회자의 숫자 비교
for k in range(25):
    check_num = numbers[k]

    # 4-1. 부른 숫자 0으로 변경
    for i in range(5):
        for j in range(5):
            if bingo[i][j] == check_num:
                bingo[i][j] = 0

    # 4-2. 빙고 체크
    if k >= 11:
        line = 0
        line += check_horizontal()
        line += check_vertical()
        line += check_diagonal1()
        line += check_diagonal2()

        # 5. 빙고이면 해당 숫자의 순서 출력
        if line >= 3:
            print(k + 1)
            break