leetcode 164 java

문제는 정렬 후 구간별로 최댓값을 출력하는 문제이다.

 

단순하게 정렬 후 출력하는게 아래 예시이다.

하지만 문제에서 시간, 공간 복잡도가 둘다 n 으로 끝나야하기 때문에,

아래는 Arrays.sort() 함수를 사용하여 nlogn 의 복잡도가 나온다.

따라서 틀린 풀이 방법이다. 하지만...

/*
정수 배열 nums가 주어졌을 때, 배열을 정렬한 후 인접한 두 요소 사이의 최대 차이를 반환하세요.
배열에 요소가 두 개 미만이라면 0을 반환하면 됩니다.

알고리즘은 선형 시간(O(n))에 실행되어야 하며, 선형 추가 공간(O(n))을 사용해야 합니다.
*/
class Solution {
    public int maximumGap(int[] nums) {
        int max = 0;
        if(nums.length < 2) {
            return 0;
        }
        else {
            Arrays.sort(nums);

            for(int i=0; i<nums.length-1; i++) {
                max = max < Math.abs(nums[i]-nums[i+1]) ? Math.abs(nums[i]-nums[i+1]) : max;
            }
            return max;
        }
    }
}

 

맞았다.. 이유는 뭔지 모르겠다. 그냥 넉넉하게 준건가. 아무튼 이건 틀린 풀이이다. 그래서

다른 방법을 사용해야한다. 그래서 chat gpt 에도움을 받아

버킷 정렬이라는 시간복잡도 o(n)인 정렬법을 찾게 되었다.

 

아래는 버킷정렬을 사용하여 풀이한 코드이다.

class Solution {
    public int maximumGap(int[] nums) {
        int result = 0;
        if(nums.length < 2) {
            return 0;
        }

        int max = 0;
        int min = Integer.MAX_VALUE;

        // 배열의 최대 최소 값 담기
        for(int i : nums) {
            max = max < i ? i : max;
            min = min < i ? min : i;
        }

        // 사이즈가 bucketSize 고 배열 갯수 bucketCount 개의 버킷 생성
        int bucketSize = Math.max(1, (max-min)/(nums.length-1));
        int bucketCount = (max-min)/bucketSize+1;
        
        // 버킷의 최대 최소 넣는 배열 생성
        int [] maxs = new int[bucketCount];
        int [] mins = new int[bucketCount];
        Arrays.fill(mins, Integer.MAX_VALUE);

        for(int i : nums) {
            // 각 요소의 값마다 어디에 넣을지 지정한다. index
            int index = (i-min)/bucketSize;

            // 최대 최소 갱신
            maxs[index] = Math.max(maxs[index], i);
            mins[index] = Math.min(mins[index], i);
        }

        // 버킷 탐색하여 구간별 최대 값 리프레시
        // 요소별 차이는 구간사이에 존재한다. 구간 내 차이로 존재 하지 않는다.
        int previous = maxs[0];
        for(int i=1; i<bucketCount; i++) {
            if(mins[i] == Integer.MAX_VALUE) {
                continue;
            }
            else {
                result = Math.max(mins[i]-previous, result);
                previous = maxs[i];
            }
        }
        

        return result;
    }
}

 

Input: nums = [3,6,9,1]

다음과 같은 배열이 존재할때,

min=9;

max=1;

이다.

bucketSize = (9-1)/3 = 2

bucketCount = (9-1)/2 + 1 = 5

 

bucketSize = (max-min) / (n-1)

bucketCount = (max-min) / bucketSize + 1

 

이다.

 

이렇게 되면

1 ~ 2 

3 ~ 4

5 ~ 6

7 ~ 8

9 ~ 10

 

의 버킷이 생기는 것이다.

 

여기서 인덱스를 계산하는

(3-1)/2 = 1 이다. 3이라는 값은 1인덱스에 들어가게 된다. 라는 공식이 나온다.

index = (value-i)/bucketSize 

 

그러면 

 

1~2 : 1

3~4 : 3

5~6 : 6

7~8 : x

9~10 : 9

 

이렇게 담기게 된다. 여기서 각 구간별 최대 최소를 구하면 끝나게 된다.

하지만 기본적인 버킷 정렬은 담은 후 다시 내부를 정렬해주어야하지만,

이건 요소 사이의 차이를 구하는 것이기 때문에, 구간내에 min, max 값만 저장하여 비교하면 된다.

 

 

그리하여 시간이 더 빨라지게 된다.

 

📌 시간 복잡도 분석 (Time Complexity)

이 알고리즘의 주요 연산을 단계별로 분석해볼게요.

1. 최댓값과 최솟값 찾기
   • 배열을 한 번 순회하며 O(n)
2. java
   복사편집
   for (int i : nums) { max = Math.max(max, i); min = Math.min(min, i); }
3. 버킷 개수와 크기 계산
   • 상수 연산이므로 O(1)
4. java
   복사편집
   int bucketSize = Math.max(1, (max - min) / (nums.length - 1)); int bucketCount = (max - min) / bucketSize + 1;
5. 버킷 배열 초기화
   • 버킷 개수는 O(n)이므로 O(n)
6. java
   복사편집
   int[] maxs = new int[bucketCount]; int[] mins = new int[bucketCount]; Arrays.fill(mins, Integer.MAX_VALUE);
7. 버킷에 숫자 할당
   • 배열을 한 번 순회하며 O(n)
8. java
   복사편집
   for (int i : nums) { int index = (i - min) / bucketSize; maxs[index] = Math.max(maxs[index], i); mins[index] = Math.min(mins[index], i); }
9. 최대 간격 찾기
   • bucketCount은 O(n)이므로 O(n)
10. java
    복사편집
    for (int i = 1; i < bucketCount; i++) { if (mins[i] == Integer.MAX_VALUE) continue; result = Math.max(mins[i] - previous, result); previous = maxs[i]; }

✅ 총 시간 복잡도:

• 모든 연산이 O(n) 이하로 수행되므로 O(n)
• 정렬(O(n log n)) 없이 선형 시간에 해결하는 것이 핵심

---

📌 공간 복잡도 분석 (Space Complexity)

1. 입력 배열(nums)
   • 입력 자체는 별도의 공간을 사용하지 않음 O(1)
2. 버킷 배열 (maxs[], mins[])
   • 버킷 개수 bucketCount ≈ n, 따라서 O(n)
3. java
   복사편집
   int[] maxs = new int[bucketCount]; int[] mins = new int[bucketCount];
4. 상수 변수 (max, min, bucketSize, bucketCount, result, previous)
   • O(1)

✅ 총 공간 복잡도:

• 추가 공간이 O(n)만큼 필요하므로 O(n)
• 입력 배열을 수정하지 않고 추가적인 메모리만 사용

---

📌 최종 정리

복잡도 유형값

시간 복잡도	O(n)
공간 복잡도	O(n)

📌 버킷 정렬을 활용하여 선형 시간 O(n)에 해결하면서도 추가 공간 O(n)을 사용함! 🚀