[알고리즘 - Java] 프로그래머스 - 진료순서 정하기(이중 for문, HashMap풀이)

문제 설명
외과의사 머쓱이는 응급실에 온 환자의 응급도를 기준으로 진료 순서를 정하려고 합니다. 정수 배열 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]

입출력 예 설명

• 입출력 예 #1
  emergency가 [3, 76, 24]이므로 응급도의 크기 순서대로 번호를 매긴 [3, 1, 2]를 return합니다.

• 입출력 예 #2
  emergency가 [1, 2, 3, 4, 5, 6, 7]이므로 응급도의 크기 순서대로 번호를 매긴 [7, 6, 5, 4, 3, 2, 1]를 return합니다.

• 입출력 예 #3
  emergency가 [30, 10, 23, 6, 100]이므로 응급도의 크기 순서대로 번호를 매긴 [2, 4, 3, 5, 1]를 return합니다.

---

풀이1 (이중 for문)

import java.util.*;

class Solution {
    public int[] solution(int[] emergency) {
    	// 입력 배열을 복제하여 정렬할 배열을 생성
        int[] asc = emergency.clone();
        // 결과를 저장할 배열 생성
        int[] answer = new int[emergency.length];
        
        // 복제한 배열을 오름차순으로 정렬
        Arrays.sort(asc);
        
        // asc 배열의 원소를 하나씩 탐색 
        for(int i=0; i<asc.length; i++) {
        	// emergency 배열의 원소를 하나씩 탐색
            for(int j=0; j<emergency.length; j++) {
            	// asc의 원소와 emergency의 원소가 일치하면
                if(asc[i]==emergency[j]) {
                	// 결과를 저장하는 배열 answer에 저장
                    answer[j]=emergency.length-i;
                }
            }
        }
        return answer;
    }
}

• answer[j]=emergency.length-i; 를 해주는 이유?
  - 정렬된 asc배열은 오름차순으로 정렬되어있기 때문에 가장 작은 숫자가 맨 앞에 위치하게 된다.
  • 따라서 원래 배열인 emergency에서 asc가 몇 번째로 작은 값인지 나타내는 순위를 계산하려면 emergency배열의 총 길이에서 i를 빼야한다.
  • 예를 들어, emergency 배열의 길이가 5라고 가정하고 i가 0일 때, asc[0]는 가장 작은 값이다.
  • 따라서 순위는 5-0=5가 된다. 제일 작은 값이기 때문에 answer배열에서 제일 마지막에 위치하게 된다.

풀이2 (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이 효율적인 이유?

이중for문을 사용하면 시간복잡도가 O(N^2)가 된다. 그러나 HashMap을 사용할 경우 시간복잡도는 O(NlogN) or O(n)수준으로 개선이 가능하다.

• HashMap은 해시 테이블을 사용하기 때문에 원소를 찾는 과정이 훨씬 빠르다. 이중for문을 통한 선형탐색보다 빠르다.
• HashMap을 사용하면 값을 키로, 해당 값의 인덱스를 값으로 매핑시키는 것이 가능하다.

따라서, HashMap을 사용하여 원소의 값을 키로 하고, 해당 값의 인덱스를 값으로 매핑하는 방식으로 알고리즘을 개선하면 성능을 향상시킬 수 있다. 이렇게 하면 이중 반복문을 사용하는 것보다 훨씬 효율적인 코드를 구현할 수 있다.