[Algo] 백준 2872 우리집엔 도서관이 있어

문제 바로가기 : https://www.acmicpc.net/problem/2872

메모리 : 32780 KB

시간 : 292 ms

언어 : Java 11

---

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int idx = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            if (arr[i] == N)
                idx = i;
        }
        int cnt = 1;
        int tmp = N - 1;
        idx -= 1;
        for (int i = idx; i >= 0; i--) {
            // 내림차순인지 검사
            if (arr[i] == tmp) {
                cnt++;
                tmp--;
            }
        }
        System.out.println(N - cnt);
    }
}

 

풀이

책이 30만권이기 때문에 구현하는 문제는 아니다. 배열을 한 번 돌면서 답을 찾을 수 있으면 최적의 풀이일 것이다. = 그리디구나!

책은 뽑아서 위로 올리는 행동밖에 할 수 없기 때문에 어떤 책을 뽑아야하는지만 결정하면 된다. 뽑아야 할 책임이 명확해지면 순서는 알아서 잘 조정할 수 있기 때문에 뽑는 순서는 고려하지 않아도 된다. 가장 밑바닥에 깔릴 책(가장 큰 수) 밑에있는 책은 모두 뽑아야하고, 그 위에 있는 책이라고 해도 순서대로 배치되어있다면 그 사이의 책이 뽑히면서 결국 정렬이 완성된다. 따라서 N, N-1, N-2... 순서로 책이 배치되어있다면 그 책은 뽑지 않아도 된다.

N의 index에서 시작해 내림차순의 책들을 골라주고, 전체 개수에서 빼면 정답이 나온다.