[LeetCode/JAVA] 561. Array Partition I

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/array-partition-i/

문제 설명

출처 : LeetCode

정수형 배열이 주어집니다.
2개씩 짝을 이뤄 두 수중 적은 값을 더한 값들 중 가장 큰 값을 반환하세요.

풀이 방법

짝을 이뤄 각 짝의 작은 값들의 최댓값을 구하려면 작은 값은 작은 값끼리 짝을 이뤄 손실을 최소화해야 함.

1. 배열을 정렬하여 작은 값끼리 짝이 되도록 합니다.
2. 배열을 정렬했으므로 최솟값은 0, 1, 3 ... 번째 인덱스의 값이 짝의 최솟값임을 이용합니다. 

간단한 예시

내 코드(JAVA)

 

public int arrayPairSum(int[] nums) {
    int maxSum = 0;

    Arrays.sort(nums);

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

    return maxSum;
}

 

다른 사람 코드

public int arrayPairSum(int[] nums) {
    int[] exist = new int[20001];
    for (int i = 0; i < nums.length; i++) {
        exist[nums[i] + 10000]++;
    }
    int sum = 0;
    boolean odd = true;
    for (int i = 0; i < exist.length; i++) {
        while (exist[i] > 0) {
            if (odd) {
                sum += i - 10000;
            }
            odd = !odd;
            exist[i]--;
        }
    }
    return sum;
}

 

정렬 메서드를 사용 및 구현하지 않고 풀이한 방법

배열 안의 num의 범위를 활용하였고, 각 값들의 자리에 +1을 해주어 값의 존재를 표시합니다.

+, - 10000을 더해주는 이유는 인덱스와 값을 맞춰주기 위함인 것 같습니다.

논리형 변수 odd를 통해 짝수번째의 값만 누적하여 더해주고, 배열에서 빼줍니다.

 

알파벳 관련 문제에서 자주 쓰던 방법을 조금 변형한 풀이인데, 생각하지 못했습니다.좋은 방법인 것 같습니다!