[99클럽 코테 스터디] 23일차 TIL - Array Partition

Hoxy?·2024년 8월 13일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

23/42

오늘의 학습 키워드

</> 탐욕법(Greedy Algorithm)

공부한 내용 본인의 언어로 정리하기

class Solution {
    public int arrayPairSum(int[] nums) {
         Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

오늘의 회고

오늘 문제는 보자마자 풀이 방법이 바로 생각나서 시작했다.
첫 마주함과 동시에 오름차순 정렬 후 2개씩 묶어서 최소 값을 구해서 더하면 되겠다고 생각했는데 배열 만들기가 좀 귀찮은데? 라는 생각을 하다가 저번에 문제에서 비슷한 느낌의 풀이가 있었던 것 같아 돌아보니 순서에 맞게 내가 필요한 순서의 인덱스 값만 가져오면 되잖아?라는 답이 떠올랐다. 그리고 풀이를 작성했다.
1. 배열을 오름차순으로 만든다.
2. 홀수번째의 인덱스값을 가져오면 최소의 희생으로 최대합을 만들 수 있다.
3. 모두 더하고 반환한다.

Arrays.sort(nums);

for(int i = 0; i < nums.length; i += 2){

}

int sum = 0;

for(int i = 0; i < nums.length; i += 2){
	sum += nums[i];
}

return sum;

오늘 문제는 복습을 열심히 한 보람이 느껴지는 문제였다.

AI 코드리뷰

현재 코드의 장점

간단하고 이해하기 쉬운 구현
Arrays.sort()를 사용하여 효율적인 정렬 수행
짝수 인덱스만 순회하여 불필요한 연산 최소화

현재 코드의 단점

원본 배열을 변경함 (정렬 과정에서)
추가 메모리 사용 없음 (in-place 정렬)

시간 복잡도

시간 복잡도: O(n log n) - Arrays.sort()의 평균 시간 복잡도
공간 복잡도: O(1) - 추가 공간을 사용하지 않음

개선 제안

원본 배열을 유지해야 하는 경우, 복사본을 만들어 정렬
정렬 대신 다른 방법을 사용하여 시간 복잡도 개선 가능

개선된 코드 제안

class Solution {
    public int arrayPairSum(int[] nums) {
        int[] count = new int[20001];
        for (int num : nums) {
            count[num + 10000]++;
        }
        
        int sum = 0;
        boolean isEven = true;
        for (int i = 0; i < 20001; i++) {
            while (count[i] > 0) {
                if (isEven) {
                    sum += i - 10000;
                }
                isEven = !isEven;
                count[i]--;
            }
        }
        return sum;
    }
}

개선된 버전의 장점