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

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

23253번: 자료구조는 정말 최고야

 

 

난이도 : 실버 5
태그 : 구현, 애드 혹, 스택, 자료 구조

 

 

설명

책 더미의 맨 위에있는 책을 꺼내, 순서대로 나열할 수 있는가에 대한 문제입니다.

 

책더미의 맨 위에서 꺼내는 것이므로,

책 더미가 애초에 내림차순으로 정렬되어 있지 않으면

책을 순서대로 나열하는 것은 항상 불가능합니다.

 

즉, 쌓여있는 책의 번호를 입력받고, 이게 내림차순 정렬이 되어있는가만 판단하면 됩니다.

 

 

 

소스코드

import sys

# 책의 개수, 책의 더미 개수
n, k = map(int, sys.stdin.readline().rstrip().split())

for i in range(k):
    sys.stdin.readline() # 책 수를 입력받지만 딱히 쓸 곳은 없으므로 그냥 입력만 받고 넘어감

    books = list(map(int, sys.stdin.readline().rstrip().split()))

    if books != sorted(books, reverse=True):
        print("No")
        exit(0)

print("Yes")

 

sorted는 기본적으로 오름차순이며, reverse=True를 통해 내림차순 정렬로 사용할 수 있습니다.

 

 

 

후기

 

처음엔 스택을 이용해 풀 수 있겠다는 생각으로 코딩을 시작했으나,

시간초과를 받고 다른 방법을 생각하였습니다.

 

참고로 본 문제 태그의 '애드 혹(Ad Hoc)'은

정형화된 알고리즘을 사용해 풀이하지 않고, 새로운 방법을 사용해 풀이하는 문제를 애드 혹 태그를 붙인다고 합니다.

 

으음... 문제를 보자마자 스택을 떠올렸는데, 이 문제에 적당한 태그 같네요 ㅎㅎ...