[백준 2872번] 우리집엔 도서관이 있어 (Python)

> 파이썬, 그리디 알고리즘

 

 

 

 

 

📖 문제 : 우리집엔 도서관이 있어 (Python)

 

 

상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다.

오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근이는 책을 알파벳 순서대로 정렬하려고 한다. 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다.

책은 1부터 N까지 번호가 책 이름의 사전 순으로 매겨져 있다. 1은 사전 순으로 가장 앞서는 책이다. 따라서, 위에서부터 책의 번호를 읽으면 (1, 2, ..., N)이 되어야 한다. 예를 들어, 책이 3권있고 처음에 (3, 2, 1)로 쌓여있을 때, 2번 만에 사전순으로 책을 쌓을 수 있다. 가장 먼저, 2번 책을 뺀 다음에 가장 위에 놓는다. 그렇게 되면 (2, 3, 1)이 된다. 마지막으로, 1을 뺀 다음 가장 위에 놓으면 (1, 2, 3)이 된다.

현재 책이 어떻게 쌓여있는지가 주어졌을 때, 몇 번만에 사전 순으로 쌓을 수 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 책의 개수 N이 주어진다. (N ≤ 300,000)

다음 N개 줄에는 가장 위에 있는 책부터 아래에 있는 책까지 순서대로 주어진다.

 

출력

첫째 줄에 몇 번만에 책을 정렬할 수 있는지 출력한다.

 

 

예제 입력 1 

3
3
2
1

 

예제 출력 1 

2

 

 

 

 

내 코드

import sys
input = sys.stdin.readline

N = int(input())

book = list(int(input()) for _ in range(N))

result = 0
check_num = len(book)
for i in range(len(book) - 1, -1, -1):
    if book[i] == check_num:
        check_num -= 1
    else:
        result += 1

print(result)

 

 

 

Point ! ⭐️ 

• 이 코드는,
  지금 책이 쌓여있는 book 리스트를 거꾸로 읽어가면서,
  그 번호가 check_num와 같으면, check_num 을 1씩 줄여주고
  아니라면, 책을 빼서 위로 올려야하는 횟수 값을 1씩 늘려주며 그 횟수를 구하는 방법입니다.
  
  예를 들어 책이 6권이 있고, 1, 3, 6, 2, 4, 5 로 쌓여 있다면
  (1, 3, 6, 2, 4, 5) -> (6, 1, 3, 2, 4, 5) -> (5, 6, 1, 3, 2, 4) -> (4, 5, 6, 1, 3, 2) -> (3, 4, 5, 6, 1, 2) -> (2, 3, 4, 5, 6, 1) -> (1, 2, 3, 4, 5, 6)
  
  보면 가장 큰 수부터 맨 뒤로 있지 않으면 다시 처음부터 위로 올려 정렬해야하기 때문에, 결국 다 빼서 위로 올려야한다는 거 !
  예제들을 하나씩 보면서 위와 같은 규칙을 세웠습니다. 
  
  만약 1, 3, 2, 4, 5, 6 으로 쌓여있다면,
  (1, 3, 2, 4, 5, 6) -> (3, 1, 2, 4, 5, 6) -> (2, 3, 1, 4, 5, 6) -> (1, 2, 3, 4, 5, 6)
  뒤에 3개의 숫자는 len(book) 값을 넣어줬던 check_num 값을 1씩 줄여가며 탐색한 것과 같은 정렬이므로
  이미 책을 빼서 다시 올릴 필요가 없으므로 앞에 3권 (1, 3, 2) 만 책을 빼서 정렬하면 되는 것입니다.
  
  규칙이 눈에 보이실까요 ?? 🧐

 

 

 

 

 

 

백준

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

2872번: 우리집엔 도서관이 있어