백준 1377 c++ : 정렬

버블정렬 코드의 순회 횟수를 구하는 문제이다. 실제로 버블정렬의 순회횟수를 구하면 시간초과가 발생한다. 정렬할 값과 인덱스 값을 묶어서 저장한 후, sort()메서드로 정렬한 후 저장된 초기 인덱스 값과 정렬 이후 인덱스 값을 비교해 가장 큰 차이 값을 구하는 방식으로 시간을 단축할 수 있다.

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

using namespace std;

void input_data(/*vector<int>& A*/ vector<pair<int, int>> &A) {
	int i, N, temp;

	cin >> N;
	//A.resize(N + 1, 0);
	A.resize(N + 1);
	for (i = 1; i <= N; i++) {
		//cin >> A[i];

		cin >> A[i].first;
		A[i].second = i;
	}

	return;
}

void find_answer(/*vector<int>& A*/ vector<pair<int, int>>& A) {
	int N = A.size() - 1; // i가 N + 1까지니까

	//기존 코드 뭉치
	//bool changed = false;
	//for (int i = 1; i <= N + 1; i++) {
	//	changed = false;
	//	for (int j = 1; j <= N - i; j++) {
	//		if (A[j] > A[j + 1]) {
	//			changed = true;
	//			swap(A[j], A[j + 1]);
	//		}
	//	}

	//	////중간 출력
	//	//cout << i << "번째 순회 : ";
	//	//for (int j = 1; j <= N; j++) {
	//	//	cout << A[j] << " ";
	//	//}
	//	//cout << "\n";

	//	if (changed == false) {
	//		cout << i << '\n';
	//		break;
	//	}
	//}
	
	//기존 코드를 사용하면 시간초과 발생
	//입력된 값을 기반으로 인덱스가 얼마나 많이 이동했는지를 판단하면 시간초과를 피할 수 있음
	//그래서 값과 인덱스 값을 모두 입력받아야 함

	sort(A.begin(), A.end());
	int count = 0;
	for (int i = 1; i <= N; i++) {
		if (count < A[i].second - i) {
			count = A[i].second - i;
		}
	}
	cout << count + 1 << "\n";

	return;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//vector<int> A;
	vector<pair<int, int>> A;

	input_data(A);
	find_answer(A);

	return 0;
}