[JAVA] 백준 21396 : 이진수 더하기

백준 21396 : 이진수 더하기

문제 설명

테스트 수 T회

N개의 수 v[i]를 입력으로 받아올림이 없는 이진수 덧셈의 결과가 x인 갯수를 구하는 문제입니다.

입력값이 크므로 long 자료형을 사용해야합니다. (35%에서 틀렸을 경우 참고)

---

풀이 방법

• 핵심은 XOR 연산의 특징을 이용하는 것입니다.
  • 받아올림이 없는 이진수 덧셈 : 1(2) + 1(2) = 0(2) , 1(2) + 0(2) = 1(2), 0(2) + 0(2) = 0(2)
  • 즉, 두개의 비트가 다르면 1, 같으면 0을 출력하는 XOR연산과 동일합니다.
• 임의의 두 수 a, b가 있다고 할 때, a ^ b = x라면, 이는 b = a ^ x와 동일합니다.
• 즉, 어떤 수 a가 존재할 때 a ^ x가 집합에 존재한다면 (a, a^x)는 조건을 만족하는 쌍입니다.
• 중복 없이 쌍을 세기 위해 맵(HashMap)을 이용해 각 수의 등장 횟수를 저장해 놓고 쌍을 계산합니다.
• 단, x = 0인 경우에는 a ^ a = 0이기 때문에, 같은 수끼리 짝짓는 경우를 따로 처리해야 합니다.

---

코드 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    //    p_21396 : 이진수 더하기
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long n = Integer.parseInt(st.nextToken());
            long x = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            HashMap<Long, Integer> v = new HashMap<>();
            for (int i = 0; i < n; i++) {
                long value = Integer.parseInt(st.nextToken());
                v.put(value, v.getOrDefault(value, 0) + 1);
            }

            long cnt = 0;
            if (x == 0) {
                for (long k : v.keySet()) {
                    long c = v.get(k);
                    cnt += c * (c - 1);
                }
            } else {
                for (long k : v.keySet()) {
                    long a = v.get(k);
                    long b = v.getOrDefault(k ^ x, 0);
                    cnt += a * b;
                }
            }
            sb.append(cnt / 2).append('\n');
        }
        System.out.print(sb);
    }
}

---

핵심 로직 설명

• x == 0일 때는 같은 숫자끼리 짝짓는 경우이므로 c * (c - 1) 방식으로 쌍의 수를 셉니다.
• x != 0일 때는 a와 a ^ x가 서로 다른 값이므로, 각 값의 빈도수를 곱해 쌍을 셉니다.
• 쌍은 (a, b)와 (b, a)로 두 번 세어지므로, 마지막 결과를 2로 나누어 중복을 제거합니다.

---

시간복잡도 & 최적화 포인트

• 시간복잡도: O(N) (맵을 통한 상수 시간 조회)
• HashMap을 통해 수의 빈도수를 효율적으로 관리
• XOR의 대칭성과 성질을 활용하여 연산 최적화

---

회고

• XOR 연산의 성질을 떠올리는 것이 핵심 포인트였다.
• 특히 x = 0일 때 예외 처리를 놓치기 쉬운데, (a ^ a = 0)이므로 동일한 수끼리 짝짓는 논리를 정확히 적용하는 것이 중요했다.
• 해시맵을 활용한 수의 빈도수 관리가 실전 문제에서도 자주 쓰이므로 익숙해져야 한다.

---

참고

[Algorithms] 비트 연산