취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 30644번 문제인 띠 정렬하기이다.
문제는 아래 링크를 확인하자.

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

주어진 띠의 인접한 두 수가 정렬된 상태에서 서로 인접하지 않는다면 이 두 수 사이는 항상 분리해야 함을 관찰하자. 절단하지 않으면 어떤 방법을 사용해도 이 두 수 사이에 다른 수가 삽입될 수 없기 때문이다. 따라서 띠의 인접한 두 수들 중 정렬된 상태에서 인접하지 않은 두 수 사이는 모두 분리해야 함을 알 수 있다.

한편, 위와 같이만 분리해도 주어진 띠를 올바르게 정렬된 띠로 항상 만들 수 있음을 관찰하자. 각 나눠진 조각은 정렬된 상태의 일부분 또는 그 역순 뿐이기 때문이다.

따라서 위의 분리해야 하는 점의 수를 세는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

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

bool comp(pair<int, int>& p1, pair<int, int>& p2) {
	return p1.second < p2.second;
}

int N;
pair<int, int> arr[200000];
int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) arr[i].first = i, cin >> arr[i].second;
	
	sort(arr, arr + N, comp);
	for (int i = 0; i < N; i++) arr[i].second = i;
	
	sort(arr, arr + N);
	for (int i = 0; i + 1 < N; i++) {
		if (abs(arr[i].second - arr[i + 1].second) > 1) ans++;
	}

	cout << ans;
}