Repository

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

1️⃣ 첫 번째 코드 분석 (이중 반복문)

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;
    }
}

📌 특징

• 각 요소에 대해 다른 모든 요소와 비교하여 순위를 매김.
• 시간 복잡도: O(N²) (이중 반복문)

🔴 단점

• 성능이 좋지 않음
  → emergency의 길이가 길어질수록 성능이 급격히 저하됨.
• 불필요한 if(answer[i] != 0) 검사가 포함됨 (이 코드에서는 불필요한 로직).
• 가독성이 떨어짐 (배열을 두 번 순회하여 index를 계산하는 것이 직관적이지 않음).

2️⃣ 두 번째 코드 분석 (정렬 + 해시맵)

import java.util.*;

class Solution {
    public int[] solution(int[] emergency) {
        int[] arr = emergency.clone();
        Arrays.sort(arr);
        Map<Integer, Integer> indexMap = new HashMap<>();
        for(int i = 0; i < arr.length; i++) {
            indexMap.put(arr[i], arr.length - i);
        }
        int[] answer = new int[emergency.length];
        for(int i = 0; i < emergency.length; i++) {
            answer[i] = indexMap.get(emergency[i]);
        }
        return answer;
    }
}

📌 특징

• emergency 배열을 정렬하여 작은 값부터 큰 값까지 순위를 매김.
• 해시맵(indexMap)을 이용하여 각 값의 순위를 빠르게 찾음.
• 시간 복잡도: O(N log N) (정렬) + O(N) (해시맵 탐색) = O(N log N)

✅ 장점

• 성능이 훨씬 좋음
  → O(N²) 대신 O(N log N)으로 성능 개선.
• 가독성이 높음
  → 정렬 후 순위를 매기는 과정이 명확하고 직관적.
• 불필요한 연산을 줄임
  → 중복 비교 없이 한 번의 정렬과 해시맵 탐색만으로 순위 결정.

3️⃣ 세 번째 코드 분석 (정렬)

import java.util.Arrays;

class solution {
    public int[] solution(int[] emergency) {
        int n = emergency.length;
        int[] answer = new int[n];
        Integer[] sortedIndex = new Integer[n];
        for( int i = 0; i < n; i++ ) {
            sortedIndex[i] = i;
        }

        Arrays.sort(sortedIndex, (i1, i2)-> emergency[i2] - emergency[i1]);

        for( int i = 0; i < n; i++ ) {
            answer[sortedIndex[i]] = i + 1;
        }

        return answer;
    }
}

📌 특징

• emergency 배열의 Index를 정렬.
• 정렬된 Index를 활용하여 각 값의 Rank를 매김.
• 시간 복잡도: O(N) (Index 적용) + O(N log N) (정렬) + O(N) (answer작성) = O(N log N)

✅ 장점

• 성능이 훨씬 좋음
  → O(N²) 대신 O(N log N)으로 성능 개선.
• 가독성이 높음
  → 정렬 후 순위를 매기는 과정이 명확하고 직관적.

4️⃣ 네 번째 코드 분석 (우선순위 큐)

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
	public int[] solution(int[] emergency) {
        int n = emergency.length;
        int[] answer = new int[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
        for( int i = 0; i < n; i++ ) {
            pq.add(new int[]{emergency[i], i});
        }

        for( int i = 0; i < n; i++ ) {
            answer[pq.poll()[1]] = n - i;
        }

        return answer;
    }
}

📌 특징

• 우선순위 큐를 활용하여 정렬된 데이터를 사용.
• 시간 복잡도: O(log n) ( PriorityQueue 요소 추가) + O(N log N) ( PriorityQueue 요소 추출) = O(N log N)

🔴 단점

• 우선순위 큐 사용시 큐 값을 꺼내는 데 추가적인 시간 오버헤드 발생

🏆 결론: 세 번째 코드가 더 낫다!

• 성능: O(N log N) vs O(N²) → 두번째와 세번째 코드가 훨씬 빠름.
• 가독성: 정렬된 배열을 활용함으로써 가독성 향상
• 유지보수성: 코드가 짧고 이해하기 쉬움.