Beakjoon] 버블 소트 (백준 1377 코테) - 정렬

문제주소 : https://www.acmicpc.net/problem/1377

1377번: 버블 소트

 

문제 :  

 

풀이 : 정렬이 필요 없어지는 데까지 몇 번의 회전이 있었는지 구하는 문제.. 코드 그대로 구하는 건 시간복잡도에서 탈락한다
그렇기에 다른 방식으로 접근해야하는데 i가 회전을 끝낸 횟수는 값이 좌측으로 이동한 수와 같다.(한 번의 i값 회전으로 좌측으론 한 칸밖에 못 움직이므로) 
그래서 인덱스값을 저장하여 sort로 정렬시키고(시간복잡도가 낮으므로) 각 수들이 좌측으로 이동한 값 중 최대의 값으로  회전을 끝낸 수를 구할 수 있다.

 

 

코드는 아래 숨김

#include <iostream>
#include <vector>
#include <algorithm>

using Numbers = std::vector<std::pair<int, int>>;

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

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int n;
	std::cin >> n;

	Numbers numbs(n);

	int temp = 0;
	for (int i = 0; i < n; ++i) {
		//std::cin >> temp;
		//numbs.push_back(std::make_pair(i, temp));
		//numbs.push_back(std::make_pair(temp,i));
		std::cin >> numbs[i].first;
		numbs[i].second = i;
		
	}

	//std::sort(numbs.begin(), numbs.end(), comp);
	std::sort(numbs.begin(), numbs.end());

	int max = 0;
	for (int i = 0; i < n; ++i) {
		temp = numbs[i].second - i;
        //temp = numbs[i].first - i;
		if (max < temp)
			max = temp;
	}
	std::cout << max + 1;

	return 0;
}

 

알게 된 것
 - 버블정렬에서 회전을 끝난때를 구하는 법을 알게 됨
 - 주석으로 처음 풀었던 흔적을 일부러 남겼는데 처음엔 인덱스를 앞에 두고 값을 뒤에 두어서 sort를 second값으로 하도록 만들었었는데 예제는 다 통과하는데 실제 제출 시 틀렸다고 나왔다. STL인 sort를 커스텀해서 사용하여서 시간초과라면 이해가 가겠는데... 아직 이해 못 하는 중 그냥 first값으로 정렬하도록 값을 넣자..