[ 백준 28116번 문제 ] 선택 정렬의 이동 거리

이번 글에서는 백준 28116번 문제를 통해 선택 정렬 알고리즘을 활용하고,
이를 통해 성능 최적화 방안을 탐구해보려 한다.
선택 정렬의 기본 개념을 바탕으로 문제 해결 과정과 효율성을 높이는 방법을 단계별로 살펴보자.

 

문제 핵심

• 이 배열은 N까지의 정수가 정확히 한 번씩 등장한다. 즉 중간에 빠진 정수나 중복된 수가 존재하지 않는다.
• 선택 정렬 알고리즘을 사용하여 주어진 배열을 정렬한다
• 이 과정에서 교환이 이루어질 때 이동한 거리를 각각 저장한다.
• N : 배열의 길이

풀이 과정

이전의 선택정렬의 문제와 같이 2중 반복을 통해 풀었다. 하지만 이번의 N의 최대길이가 다르다.

지난 번 23881번 문제에서는 N이 10,000 즉, O(N^2)의 시간 복잡도를 가지더라도 10,000,000의 연산을 한다.

하지만 이번 문제는 N이 500,000으로 어마 어마한 숫자다. 특히 자바로 문제는 푸는 나에게는 더욱 더 좋지 않은 상황이다. 

    private static void solve() {

        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                 if(arr[j] < arr[minIndex]) {
                     minIndex = j;
                 }
            }

            if(minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;

                int distance = minIndex - i;
                arrSwapCount[arr[minIndex] - 1] += distance;
                arrSwapCount[arr[i] - 1] += distance;
            }
        }
    }

 

[ 문제 ] 시간 초과

그렇다면 위 코드는 아무리 줄여나가도 2중 반복이라는 한계로 시간초과의 문제를 해결할 수 없다. 어떻게 해야 할까?

한 개의 반복문에 모두 녹여내야 한다. 코드 몇 줄 최적화 시킨다고 해서 나아질 문제가 아닌 것이다. 

 

문제 해결

문제를 고민하던 중, 제한 조건에 있던 "각 정수는 N까지 정확히 한 번씩 등장한다"는 점이 눈에 들어왔다. 이 조건을 활용하면 인덱스를 이용한 접근이 가능하다고 판단했다. 이를 바탕으로, "위치를 저장하는 배열과 기존의 정렬 대상 배열을 비교하며 값을 처리할 수 있을 것"이라는 아이디어를 떠올렸다. 그 후, 이 규칙을 기반으로 점차 로직을 구체화하며 코드를 작성했다.

 

과정은 다음과 같다. ( 백준 두 번째 예시값 )

 

1. 초기화 단계

먼저 주어진 배열이 다음과 같이 저장되고, 값의 위치를 저장하는 배열로 두개를 선언한다.

 

0부터 시작하는 특성으로 num - 1을 선언하였으나

헷갈리지 않게 사용하려면 배열을 N + 1 만큼 사용하고 0 인덱스를 제외하여 사용하면 된다.

아래 그림에 실제 가르키는 값은 다음과 같다. 제외하고 봐도 무방하다.

    private static int[] arr;
    private static int[] numLocations;

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            arr[i] = num - 1;
            numLocations[num - 1] = i;
        }

 

그림과 같이 저장된다.

 

2. 알고리즘 단계

위 그림을 보면 감이 올지도 모른다.

한 개의 반복문에서 index를 활용하여 매치 시키고, 위치에 있어야 할 값과 맞지 않는다면

해당 위치에 있는 값과 원래 있어야 하는(순서에 맞는) 값을 찾고 거리값을 구한다. 

    private static void solve() {
        for (int i = 0; i < numLocations.length; i++) {
            if (arr[i] != i) {
                int distance = numLocations[numLocations[arr[i]]] - i;

                moveCounts[i] += distance;
                moveCounts[arr[i]] += distance;

                arr[numLocations[i]] = arr[i];
                numLocations[arr[i]] = numLocations[i];
            }
        }
    }

i = 0 일때

0 = 0 ( 실제로는 1 = 1 ) 이므로 위치에 맞게 존재한다.

i = 1 일때 ( num - 1 인 것을 감안해야 한다 )

위 그림과 같이 i = 1 ( 두 번째 위치) 에 1 (2) 이 있어야 한다.

그렇다면 numLocation[1] 을 통해 원래 있어야 하는 값의 위치를 찾는다.

왼쪽부터 정렬하며 오기 때문에 i값은 항상 작다. 때문에 numLocation[i] - i를 통해 거리를 계산 할 수 있다.

또한, 값의 교환이 할 필요는 없고, i 값에 해당하는 상태는 이제 필요없기 때문에 이 후 계산할 곳에만 값을 넣어준다.

이 후 distance의 값을  moveCount 배열에 더해주면 정수마다 이동한 거리 값이 계산된다.

 

나머지도 위를 통해 문제를 해결할 수 있다.

 

선택 정렬이라고 해서 무조건 2중 반복문을 사용하는게 아닌
그 틀은 그대로 유지하며 다르게 풀어나갈 수 있다는 것
활용하는 것이 가장 중요하다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int[] arr;
    private static int[] numLocations;
    private static int[] moveCounts;

    public static void main(String[] args) throws IOException {
        prepre();
        solve();
        Arrays.stream(moveCounts).forEach(num -> System.out.print(num + " "));
    }

    private static void prepre() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        arr = new int[N];
        numLocations = new int[N];
        moveCounts = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            arr[i] = num - 1;
            numLocations[num - 1] = i;
        }
    }

    private static void solve() {
        for (int i = 0; i < numLocations.length; i++) {
            if (arr[i] != i) {
                int distance = numLocations[i] - i;

                moveCounts[i] += distance;
                moveCounts[arr[i]] += distance;

                arr[numLocations[i]] = arr[i];
                numLocations[arr[i]] = numLocations[i];
            }
        }
    }
}