24-05-18 알고리즘 문제 풀이

오늘은 JPA에 대한 이해가 부족한 것 같아서 그 부분을 찾아보면서 공부해보았다.

 

여기에는 오늘 풀어본 알고리즘 문제 하나의 풀이 과정을 적어보았다.

 

 

1. 알고리즘 문제 풀이

1-1. 풀어본 문제

leetcode에 있는 '561. Array Partition' 문제를 풀어보았다.

 

[문제]

 

2n개의 정수로 이루어진 정수 배열이 주어졌을 때, 이 정수들을 모든 i에 대한 min(ai,bi)의 합이 가장 크게 되도록 n개의 쌍[(a1,b1), (a2,b2), ..., (an,bn)]으로 그룹화하라. 가장 큰 합을 반환하라.

 

(문제 이해가 다소 어려운데, 2n개로 주어진 숫자들을 n 개의 쌍으로 모두 묶었을 때, 모든 쌍에 대해 두 수 중 작은 수들을 모두 더한 합이 최대가 되도록 만들고 그 합을 반환하는 문제이다)

 

- 예시 1

입력: nums = [1,4,3,2]

출력: 4

설명: 순서를 무시한 쌍을 그룹화하는 모든 경우의 수는 다음과 같다.

1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3

2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3

3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4

따라서 가장 큰 합은 4가 된다

 

- 예시 2

입력: nums = [6, 2, 6, 5, 1, 2]

출력: 9

설명: 최적의 쌍 조합은 (2, 1), (2, 5), (6, 6)이다.

min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

 

제한 사항:

• 1 <= n <= 10000
• nums.length == 2 * n
• -10000 <= nums[i] <= 10000

 

1-2. 문제 풀이

문제 풀이를 위한 아이디어만 떠오르면 문제 자체는 상당히 쉽게 풀린다.

 

정말 잘 생각해보면 모든 수들을 오름차순 혹은 내림차순으로 정렬한 뒤 두 개 씩 묶었을 때가 합이 최대가 된다는 것을 알 수 있다.

(1, 2), (3, 4), (5, 6), (7, 8)  (8, 7), (6, 5), (4, 3), (2, 1)

 

하나의 쌍에서 작은 값을 더해서 최대가 되려면 정렬한 뒤에 두 개씩 묶기만 하면 된다. 심지어 짝수개의 숫자가 주어진다고 문제에 주어져있기 때문에 수의 개수는 고려하지 않아도 된다.

 

나는 오름차순으로 정렬하는 법을 택했다. 오름차순으로 정렬한 뒤 쌍으로 묶게 되었을 때 두 수 중 작은 수는 왼쪽에 위치한다. 배열에서 인덱스를 생각해보면 작은 수의 경우는 짝수 인덱스를 가지게 된다. 따라서 배열을 정렬한 뒤 짝수 인덱스에 해당하는 수들만 더해주면 된다.

 

코드로 작성하면 아래와 같이 아주 간단하게 작성할 수 있다. 이전에 알게 된 구조 분해 선언을 활용해보았다.

class Solution {
    fun arrayPairSum(nums: IntArray): Int {
        var answer = 0
        
        // 배열을 정렬한다
        nums.sort()

        // 인덱스가 짝수인 수들을 모두 더해준다
        for ((index, number) in nums.withIndex()){
            if (index%2 == 0) answer += number
        }

        return answer
    }
}

위와 같이 코드를 작성했더니 바로 답안으로 통과되었다.

 

이전에 공부했던 것들을 직접 써서 문제를 풀어볼 수 있어서 좋았다. 물론 코드가 몇 줄 늘어날 뿐 이전에 알던 것 만으로도 문제를 푸는데 어려움은 없었을 것이다. 그래도 공부한 것을 단순히 알고 넘어가는 것과 직접 써볼 수 있는 것은 완전히 다른 것이라는 것을 알게된 터라 활용해서 문제를 풀어보는 경험 자체는 아주 좋은 것이라고 생각한다.

 

2. 오늘 배운 것

- JPA에 대해서 조금 더 이해할 수 있었다.

- 알고리즘 문제 풀이에 점점 익숙해지는 것 같다. 하지만 아직 참으로 갈 길이 먼 것 같다.