[Python/백준] 9291. 스도쿠 채점

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

이차원리스트

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

---

1차 풀이 - 이미 False인 경우도 계속 검사해 비효율적

import sys
input = sys.stdin.readline

n = int(input())

case = 0
for _ in range(n):
    flag = True
    case += 1
    sudoku = [list(map(int, input().split())) for _ in range(9)]
    # 중첩 반복문 들어가긴 하나, 스도쿠 판 크기 81밖에 안되니 괜찮아보임
    # 단순 구현력 묻는 문제인듯.
    for i in range(9):
        for j in range(9):
            cur_num = sudoku[i][j]
            # 행 검사
            for col in range(9):
                if col == j:
                    continue
                if sudoku[i][col] == cur_num:
                    if flag:
                        print(f'Case {case}: INCORRECT')
                        flag = False

            # 열 검사
            for row in range(9):
                if row == i:
                    continue
                if sudoku[row][j] == cur_num:
                    if flag:
                        print(f'Case {case}: INCORRECT')
                        flag = False

            # 칸 검사
            # ex. 2, 1의 경우 -> 즉, 5
            for row in range(3*(i//3), 3*(i//3) + i%3):
                for col in range(3*(j//3), 3*(j//3) + j%3):
                    if row == i and col == j:
                        continue
                    if sudoku[row][col] == cur_num:
                        if flag:
                            print(f'Case {case}: INCORRECT')
                            flag = False
    if flag:
        print(f'Case {case}: CORRECT')
    input()

---

2차 풀이 - 함수로 빼내 early return해 효율적

import sys
input = sys.stdin.readline

n = int(input())

case = 0

def is_correct():
    global case
    case += 1
    sudoku = [list(map(int, input().split())) for _ in range(9)]
    # 중첩 반복문 들어가긴 하나, 스도쿠 판 크기 81밖에 안되니 괜찮아보임
    # 단순 구현력 묻는 문제인듯.
    for i in range(9):
        for j in range(9):
            cur_num = sudoku[i][j]
            # 행 검사
            for col in range(9):
                if col == j:
                    continue
                if sudoku[i][col] == cur_num:
                    return False

            # 열 검사
            for row in range(9):
                if row == i:
                    continue
                if sudoku[row][j] == cur_num:
                    return False

            # 칸 검사
            # ex. 2, 1의 경우 -> 즉, 5
            for row in range(3 * (i // 3), 3 * (i // 3) + i % 3):
                for col in range(3 * (j // 3), 3 * (j // 3) + j % 3):
                    if row == i and col == j:
                        continue
                    if sudoku[row][col] == cur_num:
                        return False
    return True

for _ in range(n):
    if is_correct():
        print(f'Case {case}: CORRECT')
    else:
        print(f'Case {case}: INCORRECT')
    input()

 

---

정답 확인, 극한의 최적화 코드

import sys

input = sys.stdin.readline


def is_correct(sudoku):
    for line in sudoku:
        if len(set(line)) < 9:
            return False

    return True


test_case = int(input())

for t in range(1, test_case + 1):
    if t > 1:
        input()  # 스도쿠 사이 공백 무시

    sudoku1 = [list(map(int, input().split())) for _ in range(9)]
    sudoku2 = list(zip(*sudoku1))
    sudoku3 = []

    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            line = [sudoku1[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
            sudoku3.append(line)

    if is_correct(sudoku1) and is_correct(sudoku2) and is_correct(sudoku3):
        answer = "CORRECT"
    else:
        answer = "INCORRECT"

    print(f"Case {t}: {answer}")

내용 이해 자체는 되는데...

솔직히 현장에서 이정도 풀이까지 내가 떠올릴 수 있을진 모르겠다.

set() 자체가 O(n)이라서 시간복잡도 면에서도 `40ms -> 36ms`로 계산적으론 거의 비슷하고,

분석적으로도 더 효율적인진 모르겠음.

 

GPT한테 물어보니, 실제로 최적화한 마지막 풀이가 시간복잡도 면에선 더 효율적이긴 하다고 함.

두 코드의 시간 복잡도를 비교해 보면 차이가 있습니다.

---

첫 번째 코드 (zip을 이용한 검증)

시간 복잡도 분석:

1. 가로줄 검증: is_correct(sudoku1) → 각 행에 대해 set(line)을 계산 → O(9×9)=O(81)O(9 \times 9) = O(81)O(9×9)=O(81)
2. 세로줄 검증: is_correct(sudoku2) → 전치 행렬 (zip 사용) 생성 → O(81)O(81)O(81), 이후 행별 set(line) 계산 → O(81)O(81)O(81)
3. 3×3 박스 검증: is_correct(sudoku3) → 박스 추출 9개 수행 (O(81)O(81)O(81)), 이후 set(line) 계산 → O(81)O(81)O(81)

• 전체 복잡도: O(81)+O(81)+O(81)=O(243)=O(1)O(81) + O(81) + O(81) = O(243) = O(1)O(81)+O(81)+O(81)=O(243)=O(1)
  (입력 크기가 81로 고정되었으므로 상수 시간)

---

두 번째 코드 (중첩 반복문으로 직접 검사)

시간 복잡도 분석:

1. 이중 반복문을 이용한 검증:
   • 각 칸에 대해 행 검사, 열 검사, 3×3 박스 검사 수행
   • for i in range(9): for j in range(9):에서 각 셀을 기준으로:
     • 행 탐색 O(9)O(9)O(9)
     • 열 탐색 O(9)O(9)O(9)
     • 3×3 박스 탐색 O(9)O(9)O(9)
   • 최악의 경우, 모든 81개 칸에 대해 27번 비교 → O(81×27)=O(2187)O(81 \times 27) = O(2187)O(81×27)=O(2187)

• 전체 복잡도: O(2187)O(2187)O(2187) ≈ O(103)O(10^3)O(103)
  (고정된 9×9 크기에서는 여전히 상수 시간이지만, 연산량이 더 큼)

---

결론: 첫 번째 코드가 훨씬 빠름

• 첫 번째 코드: 집합(set)과 zip을 이용해 행, 열, 3×3 박스를 한 번씩만 체크 → O(1)O(1)O(1) 수준
• 두 번째 코드: 각 칸에서 중첩 반복문으로 개별 체크 → O(1)O(1)O(1)이지만 더 많은 연산 수행

실제 실행 속도 차이

테스트 케이스 수가 많아질수록 첫 번째 코드가 훨씬 빠르게 실행될 것임.
9×9보다 큰 스도쿠(예: 16×16)로 확장하면 차이가 더 커짐.

저 아이디어를 떠올릴 수 있는 근거: 

각 칸을 모두 관찰하기엔 비효율적일 듯하다. 따라서 한 뭉탱이 단위로 비교하려고 하는데,

그 비교 기능을 함수로 빼는데, 여기서 set()과 9를 비교하고자 하고, 그러기 위해서 저 set에 들어갈 인자를 1. 행, 2. 행을 리스트로 zip, 3. 각 칸을 한 줄로 변환 => 한 리스트를 요소로 가지는 2차월 리스트로 넣어서, 하나씩 빼서 비교 가능하게 데이터를 전처리했음.

===> 이 아이디어 일단 기억해두자.