23253. 자료구조는 정말 최고야 - AdHoc, 스택, 정렬. 파이썬

사용한 알고리즘 / 자료구조

1. 스택
2. 정렬
3. 힙 정렬

접근한 방법

1. 정렬을 이용한 접근법
   1. '책 더미'(스택)의 정보를 M회 입력 받는다.
   2.  '책 더미'를 입력받을 때마다 각 책 더미가 내림차순으로 정렬되어있는지 확인한다.
      1. 만약 단 하나의 '책 더미'라도 내림차순 정렬되어있지 않다면, 문제에서 요구하는 정렬 연산은 불가능하다. 
      2. 'is_order_possible'이라는 변수에 '정렬이 불가능하다'는 정보를 기입한다.
      3. 반복문을 종료한다. 
   3. '정렬' 가능 여부를 파악한다.
   4. 조건에 맞게 콘솔에 출력한다.   
2. 힙 정렬을 이용한 접근법
   1. '책 더미'(스택)의 정보를 M회 입력 받는다.
   2.  '책 더미'를 입력받을 때마다 각 책 더미의 가장 오른쪽 원소를 pop한다. 
   3. 2번에서 pop된 원소를 '책 더미'의 index값과 함께 heap 에 삽입한다.
   4. 입력 연산을 종료한다. 
   5. 책들의 heap이 빌 때까지 heappop 연산을 한다. 
      1. 5번 연산에서 '정렬 순서에 맞지 않는 책'이 등장할 경우 ->
         1. 정렬이 불가능핟고 판단한다.
         2. 'is_order_possible'에 '정렬 불가능' 정보를 기입한다.
         3. 반복문을 종료한다. 
      2. 5번 연산에서 '정렬 순서에 맞는 책'이 등장할 경우 ->
         1. 해당 원소가 등장했던 '책 더미' 가 비어있는지 확인.
         2. 책 더미가 비어있지 않다면 `책 더미`에서 pop, heap에 삽입한다. 
   6. 반복문 정렬 후, '정렬 가능` 여부를 파악한다.
   7. 조건에 맞게 콘솔에 출력한다. 

어려웠던 점

1. 약 두 달 전에 처음 풀이를 시도했던 문제다. 생소한 문제였던데다 접근법 또한 떠오르지 않아 두 달간 '어떻게 푸러야 할지' 생각했다. 

느낀 점

1. 더 많이 풀어봐야 한다.

풀이했을 당시의 백준 티어

2022-01-14, 골드 1

 

 

실행시간, 메모리, 언어

풀이 1

316ms, 53248kb, Python3

풀이 2

868ms, 79164kb, Python3

 

풀이 1: 정렬을 이용한 풀이법

from sys import stdin

# 1. 입력
# 1) 초기값 입력
N, M = map(int, stdin.readline().split())

# 2. 선언
# 1) is_order_possible: 정렬 가능 여부
is_order_possible = True

# 3. 연산 
for _ in range(M):
    stdin.readline()
    # 1) 책 더미 입력
    input_list = list(map(int, stdin.readline().split()))
    # 2) 책 더미의 정렬 여부 확인
    if input_list != sorted(input_list, reverse=True):
        # (1) 정렬 불가할 때 
        # 2 - 1 에 기입 후 break
        is_order_possible = False
        break

# 4. 출력
if is_order_possible:
    print('Yes')
else:
    print('No')

풀이 2: 힙을 이용한 풀이.

from heapq import heappop, heappush
from sys import stdin

# 1. 입력
# 1) 초기값 입력
# N: 책 수 , M :책 더미 수
N, M = map(int, stdin.readline().split())

# 2) 선언
# book_stacks: 책 더미
# book_heap: 책 힙
book_stacks = []
book_heap = []

# 3) 입력(2) - 책 더미
for index in range(M):
    stdin.readline()
    # (1) 책 더미 정보 입력
    book_stack = list(map(int, stdin.readline().split()))
    # (2) 책 더미 가장 오른쪽의 책을 pop, 힙에 삽입.
    heappush(book_heap, (book_stack.pop(), index))
    # (3) 책 더미를 book_stack에 입력.
    book_stacks.append(book_stack)

# 2. 선언
# 1) is_order_possible
# 정렬이 가능한지 여부를 나타내는 변수.
is_order_possible = True

# 3. 연산
for current_book in range(1, N+1):
    # 1) heap_pop 연산
    popped_book, stack_index = heappop(book_heap)

    # 2) heap 정렬 중 '순서'가 맞지 않을 경우.
    if current_book != popped_book:
        # (1) 정렬 불가능 기록
        is_order_possible = False
        break
    # 3) 순서가 맞을 경우
    # (1) 만약 1)의 출처 책 더미가
    # 비어있지 않을 경우
    if book_stacks[stack_index]:
        heappush(book_heap, (book_stacks[stack_index].pop(), stack_index))

# 4. 출력
if is_order_possible:
    print('Yes')
else:
    print('No')