[level 0] 진료 순서 정하기 - 문제 링크

문제 설명

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

---

제한사항

• 중복된 원소는 없습니다.
• 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]

---

나의 답안

  import java.util.Arrays;

  class Solution {
      public int[] solution(int[] emergency) {
          int[] answer = new int[emergency.length];
          int[] newArr = Arrays.copyOfRange(emergency, 0, emergency.length);

          Arrays.sort(emergency);
          for (int i = 0; i < newArr.length; i++) {
              for (int j = 0; j < emergency.length; j++) {
                  if(newArr[i] == emergency[j]) {
                      answer[i] = emergency.length-j;
                  }
              }
          }
          return answer;
      }
  }

HashMap을 이용한 풀이

import java.util.*;
class Solution {
    public int[] solution(int[] emergency) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] emergencySort = Arrays.copyOfRange(emergency, 0, emergency.length);
        Arrays.sort(emergencySort);
        int size = emergency.length;
        for(int i = 0; i<emergencySort.length; i++){
            int e = emergencySort[i];
            map.put(e, size-i);
        }
        for(int i = 0; i<emergency.length; i++){
            emergency[i] = map.get(emergency[i]);
        }
        return emergency;
    }
}

이중for문 대신 HashMap을 사용하는 이유

• HashMap은 시간복잡도 측면에서 이중 for문을 통한 탐색보다 효율적디다.
  * 이중for문 시간복잡도 : O(N^2)
  • HashMap 시간복잡도 : O(NlogN) or O(n)
• HashMap을 사용하면 값을 키로, 해당 값의 인덱스를 값으로 매핑시키는 것이 가능하다 . 따라서, HashMap을 사용하여 원소의 값을 키로 하고, 해당 값의 인덱스를 값으로 매핑하는 방식으로 알고리즘을 개선하면 성능을 향상시킬 수 있다.