[코드트리 조별과제] 정렬된 숫자 위치 알아내기 C++ 풀이

---

알고리즘 분류

• 정렬
• 구현

---

문제 설명

양의 정수를 원소로 갖는 길이가 N인 수열이 입력으로 주어졌을 때, 이 수열을 오름차순으로 정렬 했을 때 각각의 위치에 있던 원소가 어느 위치로 이동하는지 출력하는 코드를 작성해보세요.

---

입력 설명

첫째 줄에는 수열의 길이를 나타내는 양의 정수 N이 주어지고, 둘째 줄에는 N개의 양의 정수인 원소가 빈칸을 사이에 두고 주어집니다. 숫자가 중복되어 주어질 수 있습니다.

• 1 ≤ N ≤ 1,000
• 1 ≤ 수열의 원소 ≤ 1,000,00

---

출력 설명

이 수열을 정렬했을 때 각각의 위치에 있던 원소가 어느 위치로 이동하는지를 공백을 사이에 두고 출력하는 코드를 작성해보세요. 동일한 원소의 경우, 먼저 입력으로 주어진 원소가 더 앞으로 와야 합니다.

---

예제 입력

7 
3 1 6 2 7 30 1

---

예제 출력

4 1 5 3 6 7 2

---

아이디어

입력받은 숫자와 함께 입력받은 순서를 저장한다.

입력받은 숫자를 오름차순으로 정렬한 후 현재의 순서를 새로 저장한다.

기존에 입력받은 순서로 정렬한다.

아까 저장했던 순서를 출력한다.

---

알고리즘

tuple<int, int, int>가 들어있는 vec를 사용해서 처음에는 입력받은 숫자를 오름차순으로 정렬하여 새로운 순서를 저장하고

이후에는 입력받은 순서를 오름차순으로 정렬하여 새로운 순서를 출력한다.

이때 tuple의 두 번째 값을 기준으로 오름차순 정렬을 하기 위해서 cmp함수를 새로 정의하여 sort에서 사용한다.

---

코드

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
bool cmp(tuple<int,int,int> &a, tuple<int,int,int> &b)
{
    return get<1>(a) < get<1>(b);
}
int main() {
    int n;
    cin>>n;
    vector<tuple<int,int,int>> vec;
    for(int i=0,temp;i<n;i++)    
    {
        cin>>temp;
        vec.push_back(make_tuple(temp,i+1,0));
    }
    sort(vec.begin(), vec.end());
    for(int i=0;i<n;i++)
        get<2>(vec[i]) = i+1;   
    sort(vec.begin(), vec.end(), cmp);
    for(auto &a : vec)
        cout<<get<2>(a)<<" ";
    return 0;
}

---

후기

문제 링크 -> https://www.codetree.ai/missions/5/problems/indices-of-sorted-array?&utm_source=clipboard&utm_medium=text

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

sort함수와 cmp 그리고 tuple의 활용방법을 알고있다면 어렵지 않게 풀 수 있는 문제이다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!