Skip to main content

3068 - Find the Maximum Sum of Node Values

info

풀이 키워드​

스포주의

비트 조작 정렬 그리디


풀이 코드​

info
  • 메모리: 56000 KB
  • 시간: 7 ms
class Solution {
    public long maximumValueSum(int[] nums, int k, int[][] edges) {
        // 1. pre-calc XOR diff values
        int[] diff = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) diff[i] = (nums[i] ^ k) - nums[i];

        // 2. get max sum
        long ans = 0;
        for (int n : nums) ans += n;

        // sort desc
        // diff = Arrays.stream(diff).boxed().sorted(Collections.reverseOrder()).mapToInt(i->i).toArray();
        // sort asc
        Arrays.sort(diff);
        for (int i = diff.length-1; 0 < i; i-=2) {
            int diffSum = diff[i] + diff[i-1];
            if (0 < diffSum) ans += diffSum;
            else break;
        }

        return ans;
    }
}

풀이 해설​

Bit Manipulation과 Greedy 알고리즘을 이용해서 풀 수 있는 문제이다.


🔮 XOR 트릭​

XOR 연산의 특징 상 (a ^ b) ^ b = a 이므로

한 번 XOR 연산한 nums[i]는 재연산할 필요가 없음을 알 수 있다.


또한 지문에서 무조건 트리 형식의 입력이 주어진다고 했는데, 그에 따라 모든 노드가 서로 연결됨이 보장된다.

그리고 여기에 XOR의 특징을 이용하면 간선으로 이어진 인접 노드끼리가 아니더라도 XOR 연산이 가능함을 알 수 있다.

왜냐하면 예를 들어 트리가 이런 모양이라고 가정했을 때

   0
  / \
 1   2
      \
       3

간선 정보는 {{0, 1}, {0, 2}, {2, 3}} 으로 주어지겠지만, 결국 모든 노드는 건너건너 한 그래프로 연결되어있기 때문에

사이에 끼어있는 노드 0, 2를 건드리지 않고 노드 1과 3만 XOR 연산하는 것이 가능하기 때문이다.

좀 더 정확히는, {1, 0} -> {0, 2} -> {2, 3} 노드 순으로 3번 XOR 연산하는 결과가

{1, 3} 노드를 택하여 1번 XOR하는 것과 동일하다는 점을 이용하는 것이다.


⚡ Think GREEDY​

구하고자 하는 것은 XOR을 어찌저찌 잘 해서 최대 합을 구하는 것이므로

노드를 2개씩 선택해서 XOR 하여 이득인 경우만 따져보아야 할 것이다.

이득은 곧 XOR하기 전보다 커졌냐를 의미하므로 그 차를 구하면 된다. (차를 diff라고 하자.)

도출되는 diff는 크게 3가지 상황일 것인데

  1. 양수, 양수 -> 당근 이득
  2. 음수, 음수 -> 당근 손해
  3. 양수, 음수 -> ??

여기서 1, 2번은 처리가 명확하지만 3번의 경우 케이스가 갈리게 된다.

이는 도출된 양수와 음수를 합해서 그래도 양수인지(즉, 양수의 절대값이 더 큰지)에 따라 처리하면 된다.

그리고 3번에서의 음수값을 최소로 해야하기 때문에, 미리 XOR한 결과를 내림차순 정렬하여 2개씩 처리하는 것이 효율적이다.


메모​

  • 발상이 어려움.
  • XOR swap이 트리 구조에서 이렇게 활용되는게 기발하긴 하다.
  • 자바는 primitive type 역순 정렬이 구린 방식밖에 없어서 그냥 오름차순 정렬하고 거꾸로 순회했다.
    • 배열 reverse 시키는 것도 O(n)O(n)이더라. EW...