백준 2872번 : 우리집엔 도서관이 있어(그리디) ***

 

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

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

 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다. 현재 책이 어떻게 쌓여있는지가 주어졌을 때, 몇 번만에 사전 순으로 쌓을 수 있는지 구하는 프로그램을 작성하시오.

예시:

(2, 4, 3, 1) --> ( 3, 2, 4, 1) --> (2, 3, 4, 1) -->(1, 2, 3, 4)

(2, 4, 3, 1, 5) --> (3, 2, 4, 1, 5) -->(2, 3, 4, 1, 5) -->(1, 2, 3, 4, 5)

 

가장 뒤에 가야 하는 수(큰 수)가 맨 뒤에 있으면 움직이지 않아도 됨. 

아이디어 생각해내기 어려웠다..

 

문제 풀이 :

역순으로 정렬돼있는 것들은 안 건드려도 됨. 하지만 그 정렬이 깨지는 수 부터는 O(n)의 횟수를 소모해야함.

import sys

def solve(N, items):
    cnt = 0
    arange = items.copy()
    now_max = N
    reverse_sorted = []
    for i in range(N-1, -1, -1):
        if arange[i] == now_max:
            reverse_sorted.append(now_max)
            now_max = now_max-1
    move = N - len(reverse_sorted)
    return move

if __name__=='__main__':
    N = int(input())
    items = []
    for i in range(N):
        items.append(int(sys.stdin.readline()))
    ans = solve(N,items)
    print(ans)

 

 

참고: https://velog.io/@jaenny/백준-2872-우리집엔-도서관이-있어