[백준] 버블 소트 c++

문제

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

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]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

 

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

정답을 출력한다.

---

위의 코드를 그대로 사용하면 시간초과가 나게 된다. 인덱스의 최대 이동거리를 구하면 한번도 스왑하지 않는 횟수를 구할 수 있다.

 

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

using namespace std;

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

	int N = 0;
	cin >> N;

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

	int max = 0;

	//정렬전 인덱스와 정렬 후 인덱스를 비교하기 위해서 first에는 결과값, second에는 인덱스를 넣는다.
	for (int i = 0; i < N; i++)
	{
		cin >> A[i].first;

		A[i].second = i;
	}

	sort(A.begin(), A.end());


	//정렬전 인덱스 - 정렬 후 인덱스를 하게 되면 swap()을 하는 이동거리가 나오게된다.
	//최대 이동거리 == 한번도 swap이 일어나지 않는 횟수
	for (int i = 0; i < N; i++)
	{
		if (max < A[i].second - i)
		{
			max = A[i].second - i;
		}
	}

	cout << max + 1;
}

 

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