[99클럽 코테 스터디] 23일차 TIL 그리디

 

 

오늘의 문제는 LeetCode

 

561. Array Partition

 

 

문제

 

 

문제 설명 

 

2n 개의 요소로 이루어진 정수형 배열 nums가 주어집니다. 이 배열의 요소들을 n개의 쌍으로 나눈 다음 각 쌍에서 작은 값들을 선택해 그 합이 최대가 되도록 하는 값을 반환하는 문제입니다. 

 

예를 들어 nums가 [1, 4, 3, 2] 일 경우, 배열은 2n = 4개의 요소로 이루어져 있으므로 n = 2개의 쌍으로 나눌 수 있습니다. 

가능한 쌍을 나열하면 다음과 같습니다. 

1. (1, 4) (3, 2) : 작은 값 1과 2의 합은 3

2. (1, 3) (4, 2) : 작은 값 1과 2의 합은 3

3. (1, 2) (4, 3) : 작은 값 1과 3의 합은 4

따라서 가능한 합 중에서 가장 큰 값인 4가 반환되면 됩니다. 

 

 

문제 풀이 시간 

권장 풀이 시간은 30분이었고, 저는 10분이 걸렸습니다.

 

 

 

 

문제 접근 방식

먼저 예시를 확인했을 때 문제의 핵심인 오름차순 정렬을 단서로 얻을 수 있었습니다. 문제의 조건을 충족하기 위해선 주어진 배열 nums를 오름차순 정렬해야 합니다. 이유는 인접한 두 요소를 쌍으로 묶을 때 항상 작은 값이 선택 되어 합이 최대가 되도록 하는 것이 문제의 조건이기 때문입니다. 

따라서 먼저 배열 nums를 오름차순 정렬합니다. 그리고 결과를 저장할 변수 sum을 선언합니다. 반복문을 사용해 배열의 인덱스를 2씩 증가시켜 각 쌍의 작은 값을 sum에 더합니다. 마지막으로 결과를 저장한 sum을 반환합니다. 

 

 

 

문제 풀이

import java.util.Arrays;
import java.util.ArrayList;

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

 

 

코드 개선하기

Math.min 메서드를 활용해 최솟값을 구하였는데 사실 그럴 필요 없이 i 번째 요소를 sum에 더해주기만 하면 됩니다. 왜냐하면 오름차순으로 정렬된 배열에서 두 요소 중 작은 값은 항상 인덱스가 작은 요소이기 때문에 별도의 비교가 필요 없기 때문입니다. 

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; 
    }
}

 

 

 

 

 

 

 

이렇게 오늘 23일차 TIL을 작성해 보았습니다.