[프로그래머스] Lv.0 진료순서 정하기 c++

https://school.programmers.co.kr/learn/courses/30/lessons/120835

프로그래머스

 

이해가 되지 않아 한참 고민했던 문제다.

 

응급도를 기준으로 진료 순서를 정한다.

 

즉, 응급도가 높은 순서로 먼저 치료한다.

 

하지만 출력은 응급도 순서대로 정렬된 배열이 아니라, emergency 배열의 원래 순서를 기준으로 응급도를 저장해야 한다.

 

예를 들어, 환자들의 emergency가 [30, 10, 23, 6, 100]일 경우, 응급도가 높은 순서부터 보면 100이 가장 높고 6이 가장 낮다.

따라서 결과는 [2, 4, 3, 5, 1]로 출력된다.

 

그럼 어떻게 배열의 원래 순서를 기억하면서도 응급도를 저장할 수 있을까?

풀이 방법

pair 배열을 사용하면 된다.

 

1. 응급도 입력 시 pair 배열에 저장

응급도를 입력받을 때 {응급도, 원래 인덱스} 형태로 pair 배열에 저장한다.

 

2. 내림차순 정렬

이후 sort() 함수를 사용해 응급도를 기준으로 내림차순 정렬한다.

예를 들어, emergency가 [30, 10, 23, 6, 100]이라면,

•  pair로 저장한 배열은 [(30, 0), (10, 1), (23, 2), (6, 3), (100, 4)]가 된다.
• 이를 응급도 기준으로 내림차순 정렬하면, [(100, 4), (30, 0), (23, 2), (10, 1), (6, 3)]가 된다.

3. 결과 저장

결과를 저장할 answer 벡터의 크기를 emergency.size()만큼 미리 할당한 뒤,

정렬된 pair 배열을 순회하며, 원래 인덱스 위치에 rank 값을 저장한다.

여기서 rank는 1부터 시작한다(응급도는 1부터 매겨지기 때문).

 

풀이 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int,int>> datas;
vector<int> solution(vector<int> emergency) {
    vector<int> answer(emergency.size());
    for(int i=0; i<emergency.size(); i++){
        datas.push_back({emergency[i],i});
    }
    
    sort(datas.rbegin(), datas.rend());
    for(int i=0; i<datas.size(); i++){
        answer[datas[i].second] = i+1;
    }
    
    return answer;
}