[2872] 우리집엔 도서관이 있어(C++)

문제

바로가기

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

오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근이는 책을 알파벳 순서대로 정렬하려고 한다.

사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다.

책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다.

책은 1부터 N까지 번호가 책 이름의 사전 순으로 매겨져 있다. 1은 사전 순으로 가장 앞서는 책이다.

따라서, 위에서부터 책의 번호를 읽으면 (1, 2, ..., N)이 되어야 한다.

예를 들어, 책이 3권있고 처음에 (3, 2, 1)로 쌓여있을 때, 2번 만에 사전순으로 책을 쌓을 수 있다.

가장 먼저, 2번 책을 뺀 다음에 가장 위에 놓는다. 그렇게 되면 (2, 3, 1)이 된다. 마지막으로, 1을 뺀 다음 가장 위에 놓으면 (1, 2, 3)이 된다.

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

 

 

입력

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

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

 

 

출력

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

 

 

해결 방법

예시로 먼저 이해해보자.

가장 큰 책 번호부터 탐색하기 시작할 것이기 때문에 가장 큰 책 번호인 max를 8로,

그때의 인덱스인 maxi를 8로 초기화한다.

움직여야 할 책의 개수인 ans는 n이 아니라 (n - 1)로 초기화 해줘야 하는데,

그 이유는 가장 큰 책 번호는 항상 움직인 필요가 없기 때문이다!

초기 상태는 위와 같다.

maxi 가 8이므로 인덱스 1부터 7까지 돌면서 max 인 8보다 1작은 7이 존재하는지 확인한다.

 

인덱스 1 ~ 7 사이에 책 번호 7이 존재하므로 maxi = 7, max = 7로 업데이트 하고,

이 책은 뽑을 필요가 없으므로 ans를 1만큼 감소시킨다.

 

인덱스 1 ~ 6 사이에 책 번호 6이 존재하므로 maxi = 1, max = 6으로 업데이트 하고,

이 책은 뽑을 필요가 없으므로 ans를 1만큼 감소시킨다.

이제 인덱스 1 ~ 1사이에서 책 번호 5가 존재하는지 찾아야 하는데, 존재하지 않으므로 ans를 출력하고 프로그램을 종료하면 된다!

 

 

정리

1. 가장 큰 번호를 갖고 있는 책의 인덱스를 찾고
2. 인덱스 1부터 (위에서 찾은 인덱스 - 1)까지 돌면서, 가장 큰 책 번호보다 1 작은 책이 존재하는지 확인한다.
3. 존재한다면 그 책은 알맞은 자리에 있다는 소리이기 때문에 움직일 필요가 없고, 따라서 움직여야 할 책의 개수를 1만큼 감소시킨다.
4. 존재하지 않는다면 남은 책들은 모두 뽑아서 이동시켜야 한다는 뜻이므로 ans를 출력하고 프로그램 종료!

 

 

내 코드(C++)

// [2872] 우리집엔 도서관이 있어
// https://www.acmicpc.net/problem/2872

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
    int n, ans = 0; // 책의 개수, 움직여야 할 책의 개수
    int tmp, maxi, max = 0;
    vector <int> books; // 책 번호
    cin >> n;
    books.insert(books.begin(), 0); // 시작 인덱스를 1로 해주기 위해 0번째 자리에 아무값 삽입
    ans = n - 1; // 가장 큰 번호의 책은 항상 뽑을 필요가 없음
    
    for(int i = 1 ; i <= n ; i++) {
        cin >> tmp;
        books.push_back(tmp);
        if(books[i] > max) {
            max = books[i];
            maxi = i; // 가장 큰 번호를 갖고 있는 책의 위치
        }
    }
    
    for(int i = maxi - 1 ; i >= 1 ; i--) {
        if(books[maxi] == books[i] + 1) {
            maxi = i;
            ans--;
        }
    }
    cout << ans << endl;
}