백준 1377 버블 소트

문제링크

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

문제

키포인트

https://mygumi.tistory.com/84
해당 블로그의 글을 참조해 풀이했다.

내가 이해한대로 정리하면..
정렬했을때 자신의 원래 index보다 뒤에있는 원소들은 버블정렬이 진행되는동안 맨뒤에 큰 수들이 채워지면서 '매턴마다' '자기 자리를 찾을때까지' '앞으로만' '한칸씩' 간다.
(큰 수들이 뒤부터 채워지면서 앞으로 밀어냄!)
그렇기 때문에 앞으로 가장 먼 거리를 이동한 원소를 찾아내면 된다. 이를 위해 먼저 stl sort를 이용해 배열을 정렬시킨후 정렬전 index와 비교해 가장 오랫동한 이동한 원소가 이동한 거리+1을 출력하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<pair<int, int>> v;

int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num; cin >> num;
		v.push_back({ num,i });
	}
	sort(v.begin(), v.end());

	int maxn = 0;
	for (int i = 0; i < v.size(); i++) {
		maxn = max(maxn, v[i].second - i);
	}
	cout << maxn + 1;

}

후기

구현은 쉬운데 알고리즘을 생각하기가 어렵다
아직 많이 부족한듯 하다. 다음에 다시 풀어보자