[프로그래머스/C++ 문제 풀이] Lv. 0 - 특이한 정렬

문제 설명

정수 n을 기준으로 n과 가까운 수부터 정렬하려고 합니다. 이때 n으로부터의 거리가 같다면 더 큰 수를 앞에 오도록 배치합니다. 정수가 담긴 배열 numlist와 정수 n이 주어질 때 numlist의 원소를 n으로부터 가까운 순서대로 정렬한 배열을 return하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ n ≤ 10,000
• 1 ≤ numlist의 원소 ≤ 10,000
• 1 ≤ numlist의 길이 ≤ 100
• numlist는 중복된 원소를 갖지 않습니다.

입출력 예

numlist	n	result
[1, 2, 3, 4, 5, 6]	4	[4, 5, 3, 6, 2, 1]
[10000,20,36,47,40,6,10,7000]	30	[36, 40, 20, 47, 10, 6, 7000, 10000]

 

입출력 예 #1

• 4에서 가까운 순으로 [4, 5, 3, 6, 2, 1]을 return합니다.
• 3과 5는 거리가 같으므로 더 큰 5가 앞에 와야 합니다.
• 2와 6은 거리가 같으므로 더 큰 6이 앞에 와야 합니다.

입출력 예 #2

• 30에서 가까운 순으로 [36, 40, 20, 47, 10, 6, 7000, 10000]을 return합니다.
• 20과 40은 거리가 같으므로 더 큰 40이 앞에 와야 합니다.

---

문제 풀이

저는 이번 문제를 2가지 방법으로 풀어보았습니다.

 

우선 간단히 문제에 대해 설명하자면, 주어진 n으로부터 숫자들이 얼마나 떨어져있는지 체크하고 두 수의 차이가 적은 순으로 정렬하는 문제입니다.

 

우선 간편하게 sort() 함수를 통한 풀이 방법을 설명드리겠습니다.

 

sort() 함수는 자동으로 정렬을 해주는 함수입니다.

내부적으로 정렬을 하고싶은 시작점, 종료지점, 정렬 규칙을 설정할 수 있는 매개변수를 넣어줄 수 있습니다.

 

참고로 sort() 함수를 사용하기 위해서는 다음과 같은 헤더 파일이 필요합니다.

#include <algorithm>

 

여기서 중요한 점은 정렬 규칙을 설정하기 위한 함수를 bool 타입의 함수를 제작해줘야 한다는 것입니다.

 

이번 문제에서는 n을 기준으로 현재 숫자가 어느정도 떨어져있는지, 같다면 큰 수를 앞에 위치시켜야 합니다.

bool comp(int p, int n) {
    // 만약 차이가 동일한 경우라면 더욱 큰 수가 앞으로 오는 것이 true
    if (abs(prev - num) == abs(next - num)) 
        return p > n;
        
    // 차이가 동일하지 않다면 차이가 적은 수가 앞으로 오는 것이 true
    return abs(p - num) < abs(n - num);
}

 

해당 함수를 사용하여 정렬을 진행해주면 해결되는 문제입니다.

// comp 함수에서 비교에 사용하기 위해 전역 변수 추가
int num;

vector<int> solution(vector<int> numlist, int n) {
    num = n;
    
    sort(numlist.begin(), numlist.end(), comp);
    
    return numlist;
}

 

다음으로는 지금 생각해도 왜 이렇게까지 했는지 이해가 가지 않지만, map과 priority_queue를 사용해 문제를 해결하는 방법입니다.

 

제가 처음으로 풀었던 해결 방법이며 간단히 설명하자면 [map의 자동 정렬 기능 + 우선순위 큐의 자동 정렬 기능]을 통해 차이가 적은 값들을 순차적으로 저장할 수 있다는 아이디어입니다.

 

즉, map<int(차이), priority_queue<int>(정렬된 값)> 타입의 map 컨테이너를 생성하여 값을 무식하게 넣고 확인하는 방식으로 문제를 해결하였습니다.

 

정답 코드

풀이 시간 : 6m 47s

#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;

vector<int> solution(vector<int> numlist, int n) {
    vector<int> answer;

    // < n으로부터의 차, 실제 값(정렬) > 쌍을 저장하기 위한 map 컨테이너 생성
    map<int, priority_queue<int>> m;

    // 전체 숫자 리스트를 순회하기
    for (int num : numlist)
    {
        // num과 주어진 n으로부터의 차이를 key, 실제 값을 value로 map 컨테이너에 저장하기
        int key = abs(num - n);

        if (m.find(key) != m.end())
        {
            m[key].push(num);
        }
        else
        {
            priority_queue<int> pq;
            pq.push(num);
            m.insert(make_pair(key, pq));
        }
    }

    // 맵을 순회하며 answer에 값 저장
    for (pair<int, priority_queue<int>> item : m)
    {
        while(!item.second.empty())
        {
            answer.push_back(item.second.top());
            item.second.pop();
        }
    }

    return answer;
}