백준 2872번 파이썬 풀이: 우리집엔 도서관이 있어

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

 

알고리즘 분류: 그리디 알고리즘

 

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

 

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

 

문제

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

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

책은 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번 안에

 

다 움직일 수 있다.

 

그러나 나는 사실 이 문제를 풀지 못하였다.

 

자꾸 시간초과가 떠서 다른 사람들의 답을 확인하고 싶어 검색해보았으나

 

이 문제를 파이썬으로 푼 코드는 찾기가 힘들었다.

 

혹시 이 글을 보고 답을 아시는 분은 댓글을 달아주셨으면 좋겠다.

 

 

코드

 

정답은 아닌 코드지만 어떻게 풀었는지 보자면

 

책이 어떤 순서로 쌓여있는지를 book_list 라는 변수의 리스트에 저장하였다.

 

count는 아무리 많이 움직여도 book_list의 길이보다 -1만큼 작으니 이를 초기값으로 설정했다.

 

가장 큰 수를 max_num이라는 변수에 저장하고 max_num을 나타내는 인덱스는

 

max_num_idx 라는 변수에 저장하였다.

 

for문이 돌아가면서 max_num보다 1만큼 작은수가 max_num의 인덱스보다 위에 있다면

 

이 수는 움직이지 않아도 되기 때문에 count에서 1만큼 빼주었다.

 

이런식으로 계속해서 max_num을 줄여가다보면 max_num보다 1만큼 작은 수가

 

max_num보다 위에 없다면 그 때는 나머지 책들을 다 옮겨야 하기 때문에

 

count를 출력하면 된다고 생각했다.

 

시간복잡도가 그렇게 크다고 생각하지 않았는데 그냥 이 문제를 틀린건지 시간초과가 나와서

 

파이썬으로 이 문제를 푸는 정답을 아시는분을 댓글로 알려주시면 감사하겠습니다.