[백준 1517번] 버블 소트

난이도: 플래티넘 V

문제 링크: https://www.acmicpc.net/problem/1517

1517번: 버블 소트

백준 1517번 문제 버블 소트

 

분할-정복 (divide & conquer) 문제입니다.

n은 최대 50만이므로, 모든 원소에 대해 모든 다른 원소와 비교해 보는 식으로 하면 시간 초과가 납니다 (O(N^2)).

 

재귀 방식으로 배열을 구간별로 나누어 접근하도록 합니다.

나눈 구간에 대해 정렬하기 전 swap 횟수를 세고, 정렬되는 값을 별도의 배열에 기록한 후 (arr2), 본 배열 (numbers)에 반영합니다.

 

long long navigate (int start, int end) {
    if (start == end) return 0;
    
    int mid = (start + end) / 2;
    long long answer = navigate(start, mid) + navigate(mid+1, end);
    
    int i = start, j = mid+1;
    int idx = 0;
    while (i <= mid || j <= end) {
        if (i <= mid && ((j > end) || numbers[i] <= numbers[j])) {
            arr2[idx++] = numbers[i++];
        }
        else {
            answer += (mid-i+1)*1LL;
            arr2[idx++] = numbers[j++];
        }
    }
    
    for (int i = start; i <= end; i++) {
        numbers[i] = arr2[i - start];
    }
    return answer;
}

i ~ mid, mid+1 ~ end는 각각 정렬되어 있는 상태로 입력을 받습니다.

idx는 정렬된 값을 기록할 별도 배열의 인덱스입니다.

merge sort처럼 정렬을 진행한다고 볼 수 있습니다.

 

비교하는 두 값이 정렬되어 있는 경우, arr2에 앞쪽의 값을 기록하고 i를 하나 증가시킵니다.

그렇지 않은 경우, swap이 일어나는 횟수를 세어 answer에 담습니다. arr2에 뒤쪽의 값을 기록하고 j를 하나 증가시킵니다.

 

위 과정을 재귀적으로 반복하면 시간 제한에 걸리지 않고 문제를 해결할 수 있습니다.

 

채점 결과

정렬 (merge sort)과 분할 정복에 대해 잘 이해하고 있다면 쉽게 풀 수 있는 문제 같습니다.

저는 쉽게 못 풀어서... ㅠㅠ

앞에 이분 탐색 문제를 풀면서 비슷한 아이디어를 생각해 내기는 했지만

answer += (mid - i + 1) 부분은 다른 글을 참고하여 아이디어를 얻었습니다.

이런 문제를 다음에 다시 찾아와서 다른 글 참고 없이 풀어야 하는데...