[Python]백준_23253 : 자료구조는 정말 최고야

Alal11·2023년 1월 1일

출처

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

문제

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

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

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

입력

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

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

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

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

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

출력

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

제한

$1 \leq M \leq N \leq 200\,000$
$1 \leq k_i$
모든 $k_{i}$ 의 합은 항상 $N$ 이다.

예제 입출력

알고리즘 분류

구현
자료 구조
애드 혹
스택

➡️문제 분석

더미의 교과서 번호가 하나라도 역순이 되는 경우 False가 된다.
입력받은 번호는 더미의 밑에서부터 차례대로 나타낸 것이기 때문에 만약 한 구간이라도 오름차순이 된다면 교과서를 순서대로 꺼낼 수 없으므로 No를 출력한다.

➡️코드(⭕)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

check = True

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

    for j in range(i-1):
        if k[j] < k[j+1]:
            check = False
            break

    if not check:
        break

print('Yes' if check else 'No')