[Algorithm]Baekjoon 28116번 : 선택 정렬의 이동 거리

https://www.acmicpc.net/problem/28116

28116번: 선택 정렬의 이동 거리

 
 
using namespace std;
 
int n;
int arr[500001] = { 0 };
int numInfo[500001] = { 0 };
int answerCounts[500001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
 
        numInfo[arr[i]] = i;  // 특정숫자가 몇번째 인덱스에 있는지 저장.
    }
 
    for (int i = 1; i <= n; ++i)
    {
        if (arr[i] == i) continue;
 
        int targetIndex = numInfo[i]; // 현재 자리로 옮겨야 할 숫자 i가 있는 인덱스.
 
        answerCounts[arr[i]] += targetIndex - i;
        answerCounts[i] += targetIndex - i;
 
        numInfo[i] = i;
        numInfo[arr[i]] = targetIndex;
        arr[targetIndex] = arr[i];
        arr[i] = i;
    }
 
    for (int i = 1; i <= n; ++i)
    {
        printf("%d ", answerCounts[i]);
    }
}
 

 

선택정렬을 했을 때 각 원소의 이동거리를 구하는 문제이다.

N이 주어졌을 때 1~N이 각각 하나씩 주어지기 때문에 인덱스와 바로 대응이 된다.

그래서 특정숫자가 어디인덱스에 위치해있는지를 보관하는 배열을 선언해서 풀면 된다.

뭔가 딱 코테에서 쉬운문제로 나올법한 문제다. 그냥 느낌이 그렇다.