[백준 / Python 파이썬] 21396번 - 이진수 더하기

[Silver II] 이진수 더하기 - 21396

---

문제 링크

분류

비트마스킹, 자료 구조, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵

문제 설명

Albert는 최근 2진수에 대해 배워 열심히 2진수 덧셈을 연습하고 있다. 하지만 아직 익숙치 않아서 "받아 올림"을 깜빡하곤 한다.

예를 들어 3 + 5의 경우 2진수로 표현하면 11(2) + 101(2) = 1000(2) (10진수 8) 이 되어야 한다.

하지만 2진수로 표현한 두 수를 더할 때 받아 올림을 하지 않으면 11(2) + 101(2) = 110(2) (10진수 6)이 된다. 구체적으로, 20에 해당하는 가장 아래 자리를 더하면 1+1 = 0 이 되고 (올림이 발생하지만 Albert는 이를 무시한다), 21에 해당하는 자리의 수를 더하면 1+0 = 1, 마지막으로 22에 해당하는 자리의 수를 더하면 0+1 = 1이 되어 결과적으로 110(2) = 6을 얻는다.

Albert는 받아 올림이 없는 2진수 덧셈이 재밌다고 생각되어 아래와 같은 문제를 풀어보기로 했다.

n개의 정수 v[1], v[2],..., v[n]가 주어졌을 때 S(i, j)는 받아 올림 없이 2진수 덧셈으로 v[i] + v[j]를 계산한 값이라고 하자.

Albert는 임의의 정수 x에 대해 1 ≤ i < j ≤ n 과 S(i, j) = x 를 만족하는 쌍 (i, j)의 개수를 세고 싶다.

예를 들어 n = 4, v = [3 7 5 6] 그리고 x = 4 라 하자.

• S(1, 2) = 3 + 7 = 4
• S(1, 3) = 3 + 5 = 6
• S(1, 4) = 3 + 6 = 5
• S(2, 3) = 7 + 5 = 2
• S(2, 4) = 7 + 6 = 1
• S(3, 4) = 5 + 6 = 3

이 경우 조건을 만족하는 쌍은 (i, j) = (1, 2)가 유일하다.

입력으로 n, x, 그리고 n개의 정수 v[1], ..., v[n]이 주어졌을 때, Albert를 도와 조건을 만족하는 쌍의 개수를 세어보자.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 두 줄에 걸쳐 주어지는데 첫 줄에 n과 x가 공백으로 구분 되어 주어진다.

둘째 줄에는 n개의 정수가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대해 조건을 만족하는 쌍의 개수를 한 줄에 출력한다.

---

import sys
from collections import Counter
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    n, x = map(int, input().split())
    numbers = Counter(list(map(int, input().split())))

    cnt = 0

    if x == 0:
        for k in numbers.keys():
            cnt += (numbers[k] * (numbers[k] - 1))

    else:
        for k in numbers.keys():
            cnt += (numbers[k] * numbers[x ^ k])

    cnt = cnt // 2
    print(cnt)