BOJ 23253 자료구조는 정말 최고야

백준 BOJ 23253 자료구조는 정말 최고야 문제의 파이썬 python 풀이입니다.

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

문제

찬우는 스택을 배운 뒤 자료구조 과목과 사랑에 빠지고 말았다.

자료구조 과목만을 바라보기로 다짐한 찬우는 나머지 과목의 교과서 $N$권을 방 구석에 $M$개의 더미로 아무렇게나 쌓아 두었다. 하지만 중간고사가 다가오자 더 이상 자료구조만 공부할 수는 없었고, 결국 찬우는 팽개쳤던 나머지 과목의 교과서를 정리하고 번호순으로 나열하려 한다.

 N$N$권의 교과서는 각각 $1$부터 $N$까지의 번호가 매겨져 있다. 찬우는 각 더미의 맨 위에 있는 교과서만 꺼낼 수 있으며, 반드시 교과서를 꺼낸 순서대로 나열해야 하기 때문에 번호순으로 나열하기 위해서는 $1$번, $2$번, … $N - 1$번, $N$번 교과서 순으로 꺼내야 한다. 교과서를 올바르게 나열할 수 없다면 중간고사 공부를 때려치겠다는 찬우를 위해 번호순으로 나열할 수 있는지 여부를 알려주는 프로그램을 작성해 주자.

입력

첫째 줄에 교과서의 수 $N$, 교과서 더미의 수 $M$이 주어진다.

둘째 줄부터 $2\times M$줄에 걸쳐 각 더미의 정보가 주어진다.

 $i$번째 더미를 나타내는 첫 번째 줄에는 더미에 쌓인 교과서의 수 $k_{i}$ 가 주어지며, 두 번째 줄에는 $k_{i}$ 개의 정수가 공백으로 구분되어 주어진다.

각 정수는 교과서의 번호를 나타내며, 아래에 있는 교과서의 번호부터 주어진다.

교과서의 번호는 $1$부터 $N$까지의 정수가 한 번씩만 등장한다.

출력

올바른 순서대로 교과서를 꺼낼 수 있다면 Yes를, 불가능하다면 No를 출력한다.

풀이

먼저 시도했던 방법은 교과서 번호를 다 확인하면서 모든 더미를 순회하는 방식이었습니다.

시간 초과

# 23253 자료구조는 정말 최고야

import sys

# 교과서의 수 n, 교과서 더미의 수 m
n, m = map(int, sys.stdin.readline().split())

books = []

for _ in range(m):
    # 더미에 쌓인 교과서 수 k
    k = int(sys.stdin.readline())
    books.append(list(map(int, sys.stdin.readline().split())))

i = 1
while i <= n:
    for book in books:
        if book and book[-1] == i:
            i += 1
            book.pop()
            break

    else:
        print("No")
        exit()

print("Yes")

• 교과서 번호 1 ~ N까지 순서대로 하나씩 확인하는 것을, 매번 M개의 더미 모두 순회하기 때문에 최악의 경우 O(N * M) 시간 복잡도가 발생합니다.

스택 특성, top 활용

모든 스택이 내림차순으로만 쌓여 있어야 전체적으로 순서대로 꺼낼 수 있습니다.
즉, 각 스택에서 book[i] > book[i+1] 이어야 합니다.

# 23253 자료구조는 정말 최고야

import sys

n, m = map(int, sys.stdin.readline().split())

for _ in range(m):
    k = int(sys.stdin.readline())
    stack = list(map(int, sys.stdin.readline().split()))
    # 위에서부터 아래로 검사 (책 쌓인 순서대로)
    for i in range(k - 1):
        if stack[i] < stack[i + 1]:
            print("No")
            exit()

print("Yes")

• 스택 특성상 위에서부터 꺼내기 때문에, 스택 내부는 반드시 내림차순이어야만 전체적으로 1 → N 순서대로 뺄 수 있습니다
• 이 조건만 만족하면 순서대로 뽑는 것이 항상 가능하므로, 모든 스택이 내림차순인지 확인만 하면 됨!
• 이렇게 하면 스택 하나당 O(k) 검사만 하면 되기 때문에 전체 시간 복잡도는 O(N) (k₁ + k₂ + ... + kₘ = N)