Repository

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

1️⃣ 첫 번째 코드 (리스트 변환 사용)

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

class Solution {
    public int[] solution(int[] numbers, String direction) {
        List<Integer> list = Arrays.stream(numbers).boxed().collect(Collectors.toList());

        if (direction.equals("right")) {
            list.add(0, list.get(list.size() - 1)); // 마지막 원소를 맨 앞에 삽입
            list.remove(list.size() - 1); // 마지막 원소 제거
        } else {
            list.add(list.size(), list.get(0)); // 첫 번째 원소를 맨 뒤에 삽입
            list.remove(0); // 첫 번째 원소 제거
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

🔹 특징

1. 배열을 List<Integer>로 변환한 후, 리스트 연산을 통해 이동을 수행.
2. add(0, element) 또는 add(size, element)를 사용해 요소를 앞뒤로 이동.
3. 마지막에 stream()을 사용하여 다시 int[]로 변환.

🟢 장점

• 코드가 직관적이며 리스트의 메서드를 활용하여 쉽게 이해할 수 있음.

🔴 단점

• 성능이 비효율적
  • Arrays.stream(numbers).boxed().collect(Collectors.toList()) → O(N)
  • add(index, element)와 remove(index) → O(N)
  • 최종적으로 list.stream().mapToInt(Integer::intValue).toArray() → O(N)
  • 전체 시간 복잡도: O(N) + O(N) + O(N) = O(N)
• 불필요한 오토박싱 & 언박싱 발생
  • int를 Integer로 변환(boxing), 다시 int로 변환(unboxing) → 성능 저하 가능성 있음.

2️⃣ 두 번째 코드 (배열 인덱스 이동 사용)

class Solution {
    public int[] solution(int[] numbers, String direction) {
        int len = numbers.length;
        int[] answer = new int[len];
        boolean rightMove = "right".equals(direction);
        
        for (int i = 0; i < len; i++) {
            answer[rightMove ? (i + 1) % len : (i - 1 + len) % len] = numbers[i];
        }
        return answer;
    }
}

🔹 특징

1. 새로운 배열 answer을 생성하고 수학적 연산을 이용해 인덱스를 조정하여 값을 삽입.
2. 오른쪽 이동(right) → answer[(i + 1) % len] = numbers[i];
3. 왼쪽 이동(left) → answer[(i - 1 + len) % len] = numbers[i];

🟢 장점

• 성능이 매우 우수함 (O(N))
  • 단순 반복문과 인덱스 연산만 사용하여 추가적인 리스트 변환 없이 처리.
  • 리스트 변환, 박싱/언박싱이 없어 불필요한 성능 손실 없음.
• 메모리 사용량이 적음
  • int[]만 사용하므로 추가적인 객체 생성이 없음.

🔴 단점

• answer[rightMove ? (i + 1) % len : (i - 1 + len) % len] = numbers[i];
  → 가독성이 살짝 떨어질 수 있음.
  → 하지만 수학적 연산이므로 이해하면 훨씬 효율적임.

🏆 최종 결론: 두 번째 코드가 더 좋음!

첫 번째 코드 (리스트 변환) 두 번째 코드 (배열 인덱스 연산)

💡 결론:

두 번째 코드(배열 인덱스 연산 방식)이 더 빠르고 메모리 효율적이며 최적화됨.

문제: 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²) → 두번째와 세번째 코드가 훨씬 빠름.
• 가독성: 정렬된 배열을 활용함으로써 가독성 향상
• 유지보수성: 코드가 짧고 이해하기 쉬움.