[LeetCode/Medium] 1262. Greatest Sum Divisible by Three (JAVA)

문제

---

1차 풀이: PQ

nums 원소들을 다 합했을 때 3의 배수가 아니면, 그 나머지만큼의 최소한의 수를 빼주면 된다.

그럼 최솟값을 어떻게 구하느냐 했을 때, 나머지가 1이나 2인 단일 최솟값을 바로 반환하면 오답이다. 만약 나머지가 1인 수를 빼야 하는 경우에, 나머지가 2인 수를 2개 더한 것이 나머지가 1인 단일 수보다 더 작을 수 있기 때문이다. 예를 들어, 7를 빼는 것보다 2+2인 4를 빼는 게 더 최솟값인 경우가 있겠다.

그래서 최솟값을 구하기 위해 Priority Queue를 one과 two 2개를 만들고, 3으로 나눴을 때 나머지가 1, 2인 수를 저장했다.

코드

class Solution {
    public int maxSumDivThree(int[] nums) {
        
        PriorityQueue<Integer> one = new PriorityQueue<>();
        PriorityQueue<Integer> two = new PriorityQueue<>();

        int sum = 0, rest = 0;
        for (int num : nums) {
            sum += num;
            
            if (num % 3 == 1) {
                one.offer(num);
                rest += num;
            }
            else if (num % 3 == 2) {
                two.offer(num);
                rest += num;
            }
        }
        
        if (rest % 3 == 0) return sum;
            
        int removal = Integer.MAX_VALUE;
        
        if (rest % 3 == 1) {
            if (!one.isEmpty()) removal = Math.min(removal, one.poll());
            if (two.size() >= 2) removal = Math.min(removal, two.poll() + two.poll());
        }
        else if (rest % 3 == 2) {
            if (!two.isEmpty()) removal = Math.min(removal, two.poll());
            if (one.size() >= 2) removal = Math.min(removal, one.poll() + one.poll());
        }
        
        return sum - removal;
    }
}

---

2차 풀이: 그냥 변수

정답은 맞았지만, 효율성에서 그닥 좋지 않은 결과를 받았다. 최솟값 2개만 알면 되는데 굳이 PQ에 모든 수를 저장하려고 하니 비효율적이라는 생각이 들었다. 그래서 간단하게 배열에 최솟값 2개씩만 저장하도록 개선했고, 실행시간이 23ms에서 8ms로 크게 개선됐다.

코드

class Solution {
    
    private static final int INF = Integer.MAX_VALUE;
    
    public int maxSumDivThree(int[] nums) {
        
        int[] minOnes = {INF, INF};
        int[] minTwos = {INF, INF};

        int sum = 0, rest = 0;
        for (int num : nums) {
            sum += num;
            
            if (num % 3 == 0) continue;
            
            if (num % 3 == 1) update(minOnes, num);
            if (num % 3 == 2) update(minTwos, num);
            
            rest += num;
        }
        
        if (rest % 3 == 0) return sum;
        
        int removal = INF;
        
        if (rest % 3 == 1) {
            if (minOnes[0] != INF) removal = Math.min(removal, minOnes[0]);
            if (minTwos[1] != INF) removal = Math.min(removal, minTwos[0] + minTwos[1]);
        }
        
        if (rest % 3 == 2) {
            if (minTwos[0] != INF) removal = Math.min(removal, minTwos[0]);
            if (minOnes[1] != INF) removal = Math.min(removal, minOnes[0] + minOnes[1]);
        }
        
        return sum - removal;
    }
    
    private void update(int[] mins, int num) {
        if (mins[0] == INF) {
            mins[0] = num;
            return;
        }
        
        if (mins[0] > num) {
            mins[1] = mins[0];
            mins[0] = num;
            return;
        }
        
        if (mins[1] == INF || mins[1] > num) {
            mins[1] = num;
            return;
        }
    }
}