[Algorithm🧬] 백준 2578 : 빙고

문제

처음에 한 것

1. 해당 숫자 찾아서
2. 빙고판 전체에서 빙고 개수 체크

-> 5 * 5 는 통과가 되지만 만약에 입력에 더 커진다면..? 시간 초과.

import sys

readl = sys.stdin.readline

def checkBingo():
    cnt = 0
    # 가로
    for i in range(5):
        if bingo[i].count(0) == 5:
            cnt += 1

    # 세로
    for i in range(5):
        local_cnt = 0
        for j in range(5):
            if bingo[j][i] == 0:
                local_cnt += 1
        if local_cnt == 5:
            cnt += 1

    # 대각선 \
    local_cnt = 0
    for i in range(5):
        if bingo[i][i] == 0:
            local_cnt += 1
        if local_cnt == 5:
            cnt += 1

    # 대각선 /
    local_cnt = 0
    for i in range(5):
        if bingo[i][4-i] == 0:
            local_cnt += 1
        if local_cnt == 5:
            cnt += 1

    return cnt

bingo = [list(map(int, readl().split())) for _ in range(5)]
echo = []
for _ in range(5):
    echo += list(map(int,readl().split()))


# 가로 세로 대각선

for idx, e in enumerate(echo):
    breaked = False

    # 빙고판에서 숫자 찾고
    for i in range(5):
        for j in range(5):
            if bingo[i][j] == e:
                breaked = True
                bingo[i][j] = 0
                break
        if breaked:
            break

    # 빙고가 되는지 체크
    # 한번에 4로 넘어가는 경우가 있어서 >= 3
    if checkBingo() >= 3:
        print(idx + 1)
        break

입력 처리

import sys

readl = sys.stdin.readline

# 방금 지운 위치에서 가로 세로 대각선을 확인.
def checkBingo(i, j):
    global cnt

    # 가로
    if bingo[i].count(0) == 5:
        cnt += 1

    # 세로
    local_cnt = 0
    for k in range(5):
        if bingo[k][j] == 0:
            local_cnt += 1
    if local_cnt == 5:
        cnt += 1

    # 대각선 \
    local_cnt = 0
    if i == j:
        for k in range(5):
            if bingo[k][k] == 0:
                local_cnt += 1
        if local_cnt == 5:
            cnt += 1

    # 대각선 /
    local_cnt = 0
    if j == 4 - i:
        for k in range(5):
            if bingo[k][4-k] == 0:
                local_cnt += 1
        if local_cnt == 5:
            cnt += 1


bingo = [list(map(int, readl().split())) for _ in range(5)]
echo = []
for _ in range(5):
    echo += list(map(int,readl().split()))



# 빙고 숫자를 보고 위치를 바로 알 수 있게 입력 처리
b = [0] * 26

for i in range(5):
    for j in range(5):
        b[bingo[i][j]] = (i, j)
        

cnt = 0
for idx, e in enumerate(echo):
    i, j = b[e]
    bingo[i][j] = 0
    checkBingo(i, j)

    # 빙고가 되는지 체크
    # 한번에 4로 넘어가는 경우가 있어서 >= 3
    if cnt >= 3:
        print(idx + 1)
        break

빙고 탐색조차 줄임

import sys

readl = sys.stdin.readline


bingo = [list(map(int, readl().split())) for _ in range(5)]
echo = []
for _ in range(5):
    echo += list(map(int,readl().split()))


# 빙고 숫자를 보고 빙고판의 위치를 알 수 있게 딕셔너리로 저장.
b = { bingo[r][c] : (r, c) for r in range(5) for c in range(5) }

# 해당 행 / 열 / 대각선에 지워진 숫자가 몇 개 있는지 확인
cnt_r = [0] * 5
cnt_c = [0] * 5
cnt_cross1 = 0
cnt_cross2 = 0

cnt = 0

for idx, e in enumerate(echo, 1):
    # 이 위치의 행, 열, 대각선에 카운트 하나씩 올리고 빙고인지 확인.
    r, c = b[e]

    # 행
    cnt_r[r] += 1
    if cnt_r[r] == 5:
        cnt += 1

    # 열
    cnt_c[c] += 1
    if cnt_c[c] == 5:
        cnt += 1

    # 대각선 \
    if r == c:
        cnt_cross1 += 1
        if cnt_cross1 == 5:
            cnt += 1

    # 대각선 /
    if r == 4-c:
        cnt_cross2 += 1
        if cnt_cross2 == 5:
            cnt += 1

    if cnt >= 3:
        print(idx)
        break