문제

내용

외과의사 머쓱이는 응급실에 온 환자의 응급도를 기준으로 진료 순서를 정하려고 합니다. 정수 배열 emergency가 매개변수로 주어질 때 응급도가 높은 순서대로 진료 순서를 정한 배열을 return하도록 solution 함수를 완성해주세요.

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

어떤 알고리즘을 적용하려 했나요?

처음에는 큐 사용 생각을 못했다^^..

나중에 우선순위 큐를 알고 적용함

적용 근거는 무엇인가요?

응급도가 높은 순서대로 진료 순서를 정한 배열을 return하도록 라는 문장에서 힌트를 얻었다.

문제 풀이 과정에서 해당 알고리즘을 어떻게 코드로 구현하려 했나요?

PriorityQueue 자료형을 사용한다.

풀이

풀이 시간

시작 시각	종료 시각	총 소요 시간
		5분

문제 분석

제약 사항 파악 & 테스트 케이스 작성

제한사항

중복된 원소는 없습니다.
1 ≤ emergency의 길이 ≤ 10
1 ≤ emergency의 원소 ≤ 100

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

입출력 예

emergency	result
[3, 76, 24]	[3, 1, 2]
[1, 2, 3, 4, 5, 6, 7]	[7, 6, 5, 4, 3, 2, 1]
[30, 10, 23, 6, 100]	[2, 4, 3, 5, 1]

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

1차 풀이

solution(emergency) {
    // sort 한 다음에 index별로 반환~~~
}

2차 풀이

solution(emergency) {
    // 우선 순위 큐에 emergency 넣기
    // 우선 순위 큐에서 원소 빼면서 rank 매기기
}

구현

1차 풀이

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(int[] emergency) {
        return Arrays.stream(emergency)
            .map(i -> Arrays.stream(emergency).boxed()
                 .sorted(Comparator.reverseOrder())
                 .collect(Collectors.toList()).indexOf(i) + 1)
            .toArray();
    }
}

2차 풀이

import java.util.*;

class Solution {
    public int[] solution(int[] emergency) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < emergency.length ; i++) {
            pq.add(emergency[i]);
        }

        int rank = 1;
        int[] answer = new int[emergency.length];

        while (!pq.isEmpty()) {
            int front = pq.poll();
            for (int i = 0; i < emergency.length; i++) {
                if (emergency[i] == front && answer[i] == 0) {
                    answer[i] = rank++;
                    break;
                }
            }
        }
        return answer;
    }
}

복기하기

답안과 나의 풀이를 비교해보세요

추천을 가장 많이 받은 풀이

class Solution {
    public int[] solution(int[] emergency) {
        int[] answer = new int[emergency.length];

        for(int i = 0; i < answer.length; i++){
            if(answer[i] != 0){
                continue;
            }
            int idx = 1;
            for(int j = 0; j < answer.length; j++){
                if(emergency[i] < emergency[j]){
                    idx++;
                }
            }
            answer[i] = idx;
        }
        return answer;
    }
}

우선순위 큐를 사용하지 않고 정렬을 활용하였다.

요약하기

제공된 자료구조를 잘 활용하자!