https://www.acmicpc.net/problem/1517
분명 문제 이름은 버블 소트인데 버블 정렬 알고리즘으로 풀면 시간초과가 나는 아이러니한 문제
입력으로 주어진 500,000 개의 숫자를 버블 정렬 알고리즘으로 풀면 시간 복잡도 O(N^2)이 발생하기 때문이다
병합정렬
위 문제는 병합 정렬 알고리즘으로 해결해야 한다
병합정렬에 대해서는 알고리즘 - 병합정렬 을 참고 바랍니다
위 문제에서 묻고자 하는 것은 숫자가 N개 주어졌을때 정렬을 위해 버블소트 알고리즘으로 해결할 경우 숫자들 사이에서 총 몇번의 swap이 발생하느냐 ? 이다
병합 정렬 알고리즘 강의를 들을때 강사님께서 "swap횟수를 구할 경우병합 정렬 알고리즘을 활용하여 해결할 수 있는 문제 유형 중 하나" 라는 말이 떠올랐다
그래서 위 문제를 병합 알고리즘으로 해결할 수 있다라는 생각이 문득 들었다
병합정렬의 자세한 내용은 위 링크를 통해서 참고할 수 있지만 중요한 부분만 간단하게 짚고 넘어가본다면 숫자의 나열을 두개의 집합으로 나누고 정렬한 뒤 다시 병합하는 것 이라고 생각된다
따라서 위 문제에서 요구하는 swap을 알고싶을 경우 다시 병합하는 것 에 초점을 맞추면 된다
병합을 할때 왼쪽 집합과 오른쪽 집합중 더 작은 수를 최종 집합에 넣어야 하며 이때 오른쪽 집합의 원소를 넣을 경우 왼쪽 집합의 원소 개수만큼 뛰어넘는 것이므로 왼쪽 원소의 개수만큼을 count 해주면 정답이 나온다
그리고 병합정렬의 경우 시간복잡도가 O(NlogN)이 나오므로 위 문제에서 입력으로 N이 500,000이 주어지고 제한시간이 1초일 경우 시간초과가 나지 않는 것이다
위 알고리즘에서 "왜 왼쪽 원소 개수만큼을 count 해줘야 하는가 ?" 에 대해 조금 더 자세히 설명해보면 집합을 나눌때는 범위를 정하여 나누며 그 지정된 범위 내에서 정렬을 진행한 후 다시 최종 집합에 넣는다를 자세히 파악해보면 알 수 있다
결국 두개의 집합이 하나의 집합으로 합쳐진다는 것이고 이때 시점은 합치기 이전시점과 합친 후 시점인 2개로 나눠진다
합쳐질 당시 왼쪽의 집합이 최종 집합으로 간다는 것은 이미 작은수였기 때문에 정렬 알고리즘에 의해서 바꿔진 것이 아닌 원래 있을 위치였다는 의미이다
반대로 오른쪽 집합이 최종 집합으로 간다는 것은 수를 정렬해놓고 보니 해당 숫자는 합쳐질 당시의 왼쪽 숫자만큼을 뛰어넘고 앞으로 가야했었다는 의미이다
그러므로 왼쪽 숫자만큼의 수를 뛰어넘는다는 것은 그만큼 swap이 되었다는 의미와 동일하므로 이 왼쪽숫자만큼 count를 해주는 것이다
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static long[] sorted;
public static long swap;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long[] arr = new long[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Long.parseLong(st.nextToken());
}
sorted = new long[N];
merge_sort(arr, 0, N - 1);
System.out.println(swap);
}
public static void merge_sort(long[] a, int left, int right) {
/*
* left == right 즉, 부분리스트가 1개의 원소만 갖고 있는 경우
* 더이상 나눌 수 없으므로 return 한다
*/
if (left == right) {
return;
}
int mid = (left + right) / 2; // 절반 위치
merge_sort(a, left, mid); // 절반 중 왼쪽 부분 리스트 (left ~ mid)
merge_sort(a, mid + 1, right); // 절반 중 오른쪽 부분 리스트 (mid + 1 ~ right)
merge(a, left, mid, right); // 병합 작업
}
public static void merge(long[] a, int left, int mid, int right) {
int l = left; // 왼쪽 부분 리스트 시작점
int r = mid + 1; // 오른쪽 부분 리스트 시작점
int idx = left; // 채워넣을 배열의 인덱스
/**
* 왼쪽 포인터가 중간까지 가거나,
* 오른쪽 포인터가 오른쪽 끝점까지 도달했을 경우 =>
* 왼쪽 혹은 오른쪽 집합중 하나가 끝이 났다는 의미이므로
* while문을 탈출한다
*/
while (l <= mid && r <= right) {
/**
* 왼쪽 부분 리스트 l번째 원소가 오른쪽 부분리스트 r번째 원소보다 작거나 같을 경우
* 왼쪽의 1번째 원소를 새 배열에 넣고 1과 idx를 1 증가시킨다
*/
if (a[l] <= a[r]) {
sorted[idx] = a[l];
idx++;
l++;
}
/**
* 오른쪽 부분리스트 r번째 원소가 왼쪽 부분리스트 l번째 원소보다 작거나 같을 경우
* 오른쪽의 r번째 원소를 새 배열에 넣고 r과 idx를 1증가 시킨다
*/
else {
sorted[idx] = a[r];
idx++;
r++;
swap += (mid - l + 1);
}
}
/**
* 왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (l > mid)
* 오른쪽 부분리스트 원소가 아직 남아있을때
* 오른쪽 부분리스트의 나머지 원소들을 새 배열에 비교하지 않고 바로 채워준다
* 이미 정렬이 되어있으므로
*/
if ((l > mid)) {
while (r <= right) {
sorted[idx] = a[r];
idx++;
r++;
}
}
/**
* 위와 마찬가지로 오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (r > right)
* 왼쪽 부분리스트 원소가 아직 남아있을때
* 왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다
*/
else {
while (l <= mid) {
sorted[idx] = a[l];
idx++;
l++;
}
}
/**
* 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다
*/
for (int i = left; i <= right; i++) {
a[i] = sorted[i];
}
}
}
위 코드에서 swap += (mid - l + 1); 을 볼 수 있을텐데 왜 이 숫자가 나오게 되었을까 ?
왼쪽의 남은 숫자를 구하기 위해서는 현재 시점에서 가장 끝 인덱스 - 왼쪽이 가리키고 있는 인덱스 를 해줘야 하기 때문입니다
처음 이 문제를 풀때는 +1을 해주지 않아 문제를 틀렸다
왜 +1을 해주어야 하는지는 조금만 생각해보면 답이 쉽게 나올 수 있다
예를 들어 왼쪽 집합에 {1, 2, 3} 이라는 숫자가 있으며 포인터가 1(인덱스는 0)을 가리키고 있다고 가정해보자 그렇다면 인덱스는 0이고 가장 끝 인덱스는 2 이므로
mid - l 을 하게되면 2라는 값을 얻게 된다
따라서 왼쪽 집합의 개수를 구하기 위해서는 +1을 추가적으로 해주어야 정확한 답을 얻을 수 있다
좋은 풀이 감사합니다. 여러 풀이 전전하다가 여기서 깨달았습니다.