[코드트리 챌린지] 정렬된 숫자 위치 알아내기

[실력진단]

[문제]

https://www.codetree.ai/cote/13/problems/indices-of-sorted-array?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제 풀이]

원소가 주어지고 해당 원소를 정렬을 했을 때 몇번째 원소로 이동이 되는지를 파악하는 문제이다.

 

예시를 들자면 1 10 5 6 8 이라는 배열이 있을 때 이를 정렬 하면 1 5 6 8 10 이 될 것이고 이러면 1 2 3 4 5 번째 원소가 -> 1 5 2 3 4 로 이동을 한다. 이 때 1 5 2 3 4 를 구하는 문제이다.

 

사실 이 문제는 1가지 테크닉을 알면 굉장히 쉽게 풀리는 문제인데

for(int i = 0;i<n;i++){
    vec[arr[i].second] = (i + 1);
}

 

arr의 첫번째 값은 원소이며 두번째 값은 해당 위치를 저장하는 배열일때

정렬이 되어 있는 arr라는 배열에 대해서 새로운 배열 vec에 위와 같은 식을 이용하면 쉽게 값을 알 수가 있다.

 

한번 보기를 따라서 정렬을 해보자.

arr에는 처음에 {(1,1),(10,2),(5,3),(6,4),(8,5)}로 저장이 되어 있다. 이를 첫번째 원소값에 따라서 정렬을 하면

{(1,1),(5,3),(6,4),(8,5),(10,2)}로 정렬이 된다.

 

이제 이를 위의 수식에 따라서 만들어 보면

vec[arr[0].second] = 1 즉, vec[1] = 1이 된다.

vec[arr[1].second] = 2 즉, vec[3] = 2가 된다.

vec[arr[2].second] = 3 즉, vec[4] = 3이 된다.

vec[arr[3].second] = 4 즉, vec[5] = 4가 된다.

vec[arr[4].second] = 5 즉, vec[2] = 5가 된다.

 

이제 이걸 vec1부터 보자면 {1,5,2,3,4}로 답이 된다.

 

한번 봐서는 이해가 잘 안될 수 있다. 한번 스스로 따라해보면서 이해를 하도록 하자.

[회고]

이전에 비슷한 문제를 볼때는 언제나 struct를 만들고 안에 index를 넣고 이전 index와 이후 index를 파악하게 만들었는데 처음 배우고 사용해본 테크닉이었다. 까먹지 말고 가끔씩 풀면서 기억해 두자.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin>>n;
    vector<pair<int,int> > arr(n);
    for(int i = 0;i<n;i++){
        cin>>arr[i].first;
        arr[i].second = i + 1;
    }
    sort(arr.begin(),arr.end(),less<pair<int,int> >());
    vector<int> vec(n + 1);
    for(int i = 0;i<n;i++){
        vec[arr[i].second] = (i + 1);
        // cout<<vec[i]<<" ";
    }
    for(int i = 1;i<=n;i++){
        cout<<vec[i]<<" ";
    }
    return 0;
}