[C/C++] 백준 1377번 - 버블 소트

✏️ 문제 링크

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

1377번: 버블 소트

 

✏️ 문제 설명

 

✏️ 문제 풀이

  false일 때 출력되기 위해서는 버블 정렬 중 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 게 핵심 

 이중 for문을 다 돌리기에는 N의 값이 크기 때문에 버블 정렬로 풀면 시간 초과가 발생할 수 있음

 vector를 생성해 pair쌍으로(입력값, 인덱스) push해주고 sort알고리즘을(O(nlogn)) 통해 vector를 정렬

 정렬 전 인덱스와 정렬 후 인덱스를 비교하여 최댓값을 찾은 후 +1(swap이 일어나지 않는 반복문이 한 번더 실행)

 

✏️ 문제 코드

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	vector<pair<int,int>>A(N);

	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		A[i].first = x; 
		A[i].second = i; 
	}

	sort(A.begin(), A.end()); 
	int max = 0;

	for (int i = 0; i < N; i++) {
		int temp = A[i].second - i;
		if (max < temp)
			max = temp;
	}

	cout << max + 1;
}