[알고리즘] 백준 1838번: 버블 정렬 (C++), 더 논리적인 감각을 만들어내야 한다

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

1838번: 버블 정렬

 

이번 문제는 논리적인 접근이 꽤 어려웠던 문제다.

처음에는 저걸 어떻게 최적화시켜야 할까를 한참 고민하다가 버블 정렬 말고도 퀵 정렬 힙 정렬의 구현 코드를 가져와서 풀어봐야 할까 했지만 암만 생각해도 체계 자체가 다른데 i를 못 구할 거 같았다.

그래서 생각해냈던 건 '정렬 된 것과 정렬되지 않은 배열에서의 차이점에서 뭔가를 구할 수는 없을까?'가 핵심이었다.

 

---

논리

생각해냈던 접근으로 논리에 쉽게 접근할 수 있었다.

버블 정렬은 한 줄을 돌며 swap 할 것이 있으면 한 줄을 돌면서 swap을 해낸다. swap을 하고도 swap 해야 할 것이 남았다면 다시 한 줄을 돌며 swap을 한다. 한 줄을 돌 때마다 i가 하나씩 더해지는 것을 이용해 문제를 풀 수 있었다.

정렬된 배열과 정렬되지 않은 배열에서 각 인덱스 위치를 비교하며 제일 차이가 많이 나는 차의 값을 구하면 그 차가 한 줄을 몇 번 돌았는지 알 수 있는 열쇠였다.

 

하지만 배열의 원소 개수가 500,000까지의 범위를 가진다는 점에서 이분 탐색을 떠올릴 수 있어야 했다. 이번 문제는 포인트가 2개였다. 특히 첫 번째 포인트를 떠올리는 게 제일 어려웠던 거 같다.

---

논리가 끝나지만 코드는 틀렸었다

다음 코드는 몇 번이나 수정하고, 뜯었던 코드지만 시간 초과가 되어 돌아온 코드다.

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

int BS(vector<int> arr2, int low, int high, int findIdx) {
	while (low <= high) {
		int mid = (low + high) / 2;

		if (arr2[mid] > findIdx) {
			high = mid - 1;
		}
		else if (arr2[mid] < findIdx) {
			low = mid + 1;
		}
		else {
			return mid;
		}
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vector<int> arr;
	vector<int> arr2;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		arr.push_back(a);
		arr2.push_back(a);
	}

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

	int temp;
	int maxIdx = 0;
	for (int i = 0; i < n; i++) {
		temp = BS(arr2, 0, n - 1, arr[i]); // BS == binary search
		//cout << temp << ' ' << i << '\n';
		maxIdx = max(i - temp, maxIdx);
	}

	cout << maxIdx;
	return 0;
}

몇 번이나 뜯고 수정했는지 논리에는 확실히 자신이 있었다. 예상 시간 복잡도도 범위 안에 속해있었다.

그러다가 다른 사람들의 코드를 보면서 어디가 문제인지 파악을 한 시간 넘어가도록 했었지만 찾을 수 없었다. 딱 하나 다른 점이 있었는데 바로 이분 탐색에 들어가는 배열에 '&(참조 연산자)'가 붙어 들어갔던 것이다.

혹시나 하는 마음에 붙여줬더니 통과를 했다. 이 포스팅에서는 논리까지 설명하고, 다음 포스팅에서는 미뤄왔던 포인터를 공부하여 포스팅해야 할 거 같다..😂😂

---

+추가: 포인터 관련 포스팅

https://draw-code-boy.tistory.com/41

[C++] 포인터 개념, 백준 1838번: 버블 정렬 (2)