[Python] 백준 23253. 자료구조는 정말 최고야

문제

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

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

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

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

입력

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

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

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

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

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

출력

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

제한

•  1≤M≤N≤200000
•  1≤ki
• 모든 ki의 합은 항상 N이다.

---

풀이

1초, 1024mb 제한이 있던 문제였다. 원래 처음에는 1번 찾고 다른 책들 쌓인 곳을 돌아서 2번 찾고 찾을 수 없다면 break하는 형식으로 코드를 짰었는데... 시간초과가 떴었다. 어찌보면 당연한 일...

왜냐하면 M이 최대 200000이고 N도 동일하니까 순서를 찾기 위해서...O(M*N)이고 이건 4*10^10이다... 보통 1초가 10^8이니까 완전히 시간초과다!! 

 

시험 중에 풀었던 문제라 이후에 맞은 친구한테서 힌트를 얻었는데... 

1. 어차피 숫자는 한번씩 밖에 안나옴

2. 책이 쌓여있는 순서가 아래서부터 위까지 점점 작아지지 않으면 어차피 어떤 상황이든 성립할 수 없다는 것.

이었다... 이거 완전 유레카잖아....

 

이를 바탕으로 코드를 작성해보면...

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
data = []
state = True

for i in range(m):
    k = int(input())
    data.append(list(map(int, input().split())))

for i in range(m):
    num = 0
    for j in range(len(data[i])):
        if j == 0:
            num = data[i][j]
        if data[i][j] > num:
            state = False
            break
        else:
            num = data[i][j]
    if state == False:
        break

if state:
    print("Yes")
else:
    print("No")

 

위와 같다. 그냥 data라는 배열에 배열들을 저장해두고 돌면서 맨 처음에 들어오는(맨밑에 깔리는 숫자보다 큰 수라도 들어오는) 순간 모든 반복문을 break하고 나와서 "no"를 출력하게끔 했다. 

 

 

시간복잡도

위 코드의 시간복잡도는... 모든 책이 한번씩만 나오기 때문에 O(N+M)이다. 대충... 400000일테고 이는 4*10^5일테니 꽤 괜찮은 것 같다.