[프로그래머스 Lv0] 진료순서 정하기 | 자바

문제

진료순서 정하기

풀이1

import java.util.*;
 
class Solution {
    public int[] solution(int[] emergency) {
        int[] answer = new int[emergency.length];
 
        int[] copied = emergency.clone();
        Arrays.sort(copied);
 
        for(int i = 0; i < emergency.length; i++) {
            for(int j = 0; j < copied.length; j++) {
                if(emergency[i] == copied[j]) answer[i] = emergency.length - j;
            }
        }
 
        return answer;
    }
}

풀이2

처음에 푼 이중 for문보다 HashMap으로 문제를 해결하는게 더 효율적입니다. 이중 for문을 사용하면 시간 복잡도가 최대 O(N^2)가 되는데, HashMap을 사용할 경우 O(NlogN) 또는 O(N)까지 개선이 가능하기 때문입니다.

import java.util.*;
 
class Solution {
    public int[] solution(int[] emergency) {
        int[] answer = new int[emergency.length];
        int rank = 1;
 
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < emergency.length; i++) {
            map.put(emergency[i], i);
        }
 
        int[] copied = emergency.clone();
        Arrays.sort(copied);
 
        for(int i = copied.length - 1; i >= 0; i--) {
            int idx = map.get(copied[i]);
            answer[idx] = rank;
            rank++;
        }
 
        return answer;
    }
}