백준 28116번 - 선택 정렬의 이동 거리

문제

• 백준, 실버 3, https://www.acmicpc.net/problem/28116
• 풀이 날짜: 2025.3.22
• 풀이 시간: 19:48~19:55, 21:45~21:56(총 18분)
• 알고리즘 분류: 구현, 정렬
• 사용 언어: C++

문제 해설

선택 정렬에서 각 수의 이동 거리를 계산하는 문제.

n의 크기를 보면 최대 500000이므로, O(n^2)의 알고리즘으로는 해결할 수 없다.

그러나 중요한 것은 수를 직접 정렬하는 것이 아니기 때문에 O(n^2)보다 더 빨리 해결할 방법이 있다는 것이다.

실제로는 선택 정렬에서 수의 교환 횟수는 (n-1)번이다. 선택 정렬에서 가장 시간이 오래 걸리는 작업은 수의 위치를 파악하는 것으로 매 iteration마다 최대 n번의 비교 연산이 필요하다. 이 비교 연산의 횟수를 낮출 수 있다면, 예를 들어 O(1)로 낮춘다면 전체 연산 시간은 O(1) * n = ~O(n)으로 최적화할 수 있다.

이때 각 수의 위치를 O(1)의 시간에 발견하려면, 각 수마다의 위치를 기록해놓은 배열을 만들면 된다. 1부터 n까지의 수는 단 한 번씩만 등장하기 때문에, 길이 n의 배열로 모든 수의 위치를 기록할 수 있다.

이 과정에서 세 개의 배열이 필요한데,

1. 정렬을 진행할 배열
2. 각 수의 위치를 저장하는 배열
3. 각 수의 이동 거리를 저장하는 배열

이렇게 정리할 수 있다.

그리고 이 문제를 해결하기 위한 알고리즘은 이와 같이 정리할 수 있다.

28116 해결 전략
1. 1부터 n까지의 수, 각자 자신의 위치를 기록해놓는다
2. 각 수마다 이동 횟수는 0으로 지정한다
3. i번째 차례에는 수 i의 위치와 i번째 위치에 있는 수의 위치를 바꾼다
4. 이때, 수 i와 i번째 위치의 수의 이동 횟수는 (수 i의 위치) - i만큼 증가한다.
(수 i가 i번째 위치에 있는 수보다는 오른쪽에 있거나 같기 때문에, (수 i의 위치)는 i보다
무조건 크거나 같다.)

전체 풀이를 정리하면 이와 같다.

#include <iostream>
#include <cstring>

using namespace std;

void swap(int* pa, int* pb)
{
    int temp = *pa;
    *pa = *pb;
    *pb = temp;
}

int main()
{
    int n;
    int arr[500001];
    int posArr[500001];
    int movementsArr[500001];
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    memset(movementsArr, 0, sizeof(int) * (n+1));

    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        posArr[arr[i]] = i;
    }

    for (int i = 1; i < n; i++)
    {
        // 이동 횟수 및 i번째 수 저장
        int move = posArr[i] - i;
        int temp = arr[i];
        
        // 수의 위치를 바꾼다.
        swap(&arr[i], &arr[posArr[i]]); // i번째 수와 수 i를 바꾼다.
        swap(&posArr[temp], &posArr[i]); // 위치도 함께 교환

        // 이동 횟수 증가
        movementsArr[i] += move;
        movementsArr[temp] += move;
    }

    // 결과 출력하기
    for (int i = 1; i <= n; i++)
        cout << movementsArr[i] << " ";

    return 0;
}