코드포스 (Codeforces Round #765(Div.2)) A. Ancient Civilization

 

 

[문제설명]

 과학자들이 목성의 위성인 가니메데(Ganymede) 고대문명을 발견하였다. 그 고대문명의 언어는 2개의 알파벳을 사용하고 각 단어는 정확하게 길이가 ℓ이다. 그래서 이 언어의 각 단어를 0에서 2ℓ-1까지의 정수로 쓰기로 하였다. 주어지는 단어에 대하여 '규칙'을 만족하는 단어 y를 찾아야 한다. 

 단어의 왼쪽부터 오른쪽으로 거리를 구한다. 1001(2)와 1100(2)인 두 단어 사이의 거리는 2이다. 좌에서 우로 볼 때 2번과 4번이 서로 다르기 때문에 거리가 2이다. 주어지는 단어들과 찾아내야하는 단어인 y의 거리는 최소가 되어야하고, y의 값도 최소가 되어야 한다.

 

주어진 정수를 2진법으로 바꿔준다.

2진법으로 바꾼 정수를 위에서 아래로 1열로 세운뒤 각 자리마다 1이 많이 있는지 0이 많은지 세어 더 많은 것으로 y를 구성한다(같으면 0을 가져온다. y는 최소가 되어야 하기 때문에)

 

예제 1)
n:3, ℓ:5, 정수: 18, 9, 21

입력받은 정수들을 2진법을 바꿔 줄세워준다.

18:  1 0 0 1 0 

9 :   0 1 0 0 1 (ℓ이 5이므로 앞에 0을 붙여줘야 한다.)

21:  1 0 1 0 1 

-----------------

y :   1 0 0 0 1 (=17) (규칙에 따라 y를 만들어준다. 만약, 1과 0의 개수가 같으면 0을 가져온다.)

 

 

 

#python

t=int(input())
for _ in range(t):
    n,l=map(int,input().split())
    arr1=list(map(int, input().split()))
    arr2=[]
    for i in arr1:
        arr2.append("{0:b}".format(i).zfill(l))

  
    result=[]
    y=0
    #print(arr2)
    for i in range(l):
        d=0
        for j in range(n):
            if(int(arr2[j][i])==0):
                d+=-1
            else:
                d+=1

        if(d>0):
            result.append(1)
        else:
            result.append(0)

        #print(result)
    for i in range(l):
        y+=result[i]*2**(l-1-i)

    print(y)