561. Array Partition I

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

Array Partition I - LeetCode

[문제 설명]

전체의 개수가 짝수인 정수형 배열이 있습니다. 숫자 두개씩 묶어서 작은값들의 총합을 구합니다.

총합의 가장 큰 수가 되려면 뭐가 되야할까요.

예시 ) 1,4,3,2가 있으면

(1,4,) (3,1) -> 1,4 중 최소값은 1 + 3,1 중 최소값은 1 -> 4가 나오는데 이 경우가 나올 수 있는 경우의 수 중에서 가장 큰 수이다.

 

[처음 생각한 접근 방법]

풀어봤던 문제같은 느낌이 드는데 체크가 안되어있는 걸 보면, 프로그래머스에서 풀어봤거나 비슷한 문제를 풀어본 거 같다.

일단 최대의 수가 나오려면, 당연히 가장 큰 수들이 나와야 한다. 문제는 그 수가 나오려면 역설적이게도 그보다 큰 숫자가 필요하다.

 

위처럼 배열이 있다고 했을 때, 가장 큰 값이 나오려면 3,4가 나와야한다.

허나 3과 4가 나오려면 그보다 큰 수가 필요하다. 이로 인해 단순히 가장 큰 수를 뽑는 건 안된다는 걸 볼 수 있다.

 

그렇다면, 가장 큰 수가 나오려면 어떻게 해야할까? 일단 현재 상태에서 4는 가장 큰 수이므로 나올 수 없다.

그렇다면 3은? 4가 존재하므로 나올 수 있다.

 

가장 큰 수와 두번째로 큰수를 순서대로 뽑는다.

그리고 두번째로 큰 수를 총합에 더한다.

 

가장 큰 수와 두번째로 큰 수를 뽑자.

총합은 3이 됐고, 남은 수는 1,2 마저 반복하자.

 

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;

        //nums.length-2까지 가야 마지막 두번째로 큰 숫자임.
        for (int i = nums.length-2; i >= 0 ; i-=2) {
            sum += nums[i];    
        }

        return sum;
    }
}

 

[리트코드 최다 추천 답안]

Java Solution, Sorting. And rough proof of algorithm. - LeetCode Discuss

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

사실상 답이 똑같다. 이 글을 쓴 사람은 0부터 시작했지만, 나는 끝에서부터 시작했다는 차이 정도.

사실 나도 처음에 0부터 시작했지만, 그림 예시에 코드를 맞추다보니 끝에서부터 시작하게 됐다.