[백준 / C++] 2872번 우리집엔 도서관이 있어

문제

설명

책 순서대로 정렬하는데, 책을 정렬 할 수 있는 방법은 책을 빼서 맨 위에 올려놓는 방법 뿐이다.

입력 받은 책을 나열하고, 뒤에서부터 읽어 순서가 맞지 않은 책의 개수가 정답이다.

뒤에서부터 읽을 때 책이 연속적으로 순서가 맞지 않아도 된다.

코드

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

int N; // 책의 개수
int answer; // 정답

int main() {

	cin >> N;

	answer = N;

	vector<int> book(N);

	for (int i = 0; i < N; i++) {
		cin >> book[i];
	}

	vector<int> sortedBook(N);
	copy(book.begin(), book.end(), sortedBook.begin());

	sort(sortedBook.begin(), sortedBook.end());

	int current = N - 1;

	for (int i = N - 1; i >= 0; i--) {
		if (book[i] == sortedBook[current]) {
			answer--;
			current--;
		}
	}
	
	cout << answer;

	return 0;
}