백준 1517번 버블 소트

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

배열을 반으로 나누어서 탐색하며 접근해야했던 문제였습니다.

버블소트는 해당 인덱스를 기준으로 다음 인덱스를 비교했을 때, 해당 인덱스에 위치한 값의 우선순위가 더 작다면 swap하는 정렬 기법입니다.

알고리즘은 아래와 같습니다.

1. 배열을 반으로 쪼개며 inversion 즉, 해당 인덱스보다 다음 인덱스의 우선순위가 작은 지점을 탐색합니다.

2. 탐색을 하는 과정에서 머지 소트처럼 다른 배열에 값을 업데이트합니다.

i) 순서가 맞다면 그대로 넣어줍니다.

ii) 우선순위가 반전되있는 상태라면 반전되어있는 길이를 결과에 더해주고 순서에 맞게 넣어줍니다.

3. 2번에서 업데이트한 배열을 토대로 기존 배열을 업데이트해줍니다.

#include <iostream>

using namespace std;

 

const int MAX = 500000;

 

int arr[MAX], arr2[MAX];

 

long long func(int start, int end)

{

        //탈출 조건

        if (start == end)

                 return 0;

 

        int mid = (start + end) / 2;

        //반으로 분할하여 탐색

        long long result = func(start, mid) + func(mid + 1, end);

 

        int i = start;

        int j = mid + 1;

        int idx = 0;

        while (i <= mid || j <= end)

        {

                 //순서대로 잘 있다면 그냥 추가해주고

                 if (i <= mid && (j > end || arr[i] <= arr[j]))

                         arr2[idx++] = arr[i++];

                 //mid를 기준으로 왼쪽의 inversion 개수 파악

                 else

                 {

                         result += (mid - i + 1) * 1LL;

                         arr2[idx++] = arr[j++];

                 }

        }

        //배열 업데이트

        for (int k = start; k <= end; k++)

                 arr[k] = arr2[k - start];

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i];

 

        long long result = func(0, N - 1);

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~