백준 3460번- '이진수' (PYTHON 풀이)

문제:

 

It 관련 전공이나 수업을 듣게 된다면 반드시 한번쯤은 배우거나 들었을 이진수 문제이다.

이진수를 구할 테스트 케이스를 입력받고, 각 테스트 케이스에 대해서 이진수로 변환했을 때, 1의 위치를 공백으로 구분해서 한 줄로 출력하면 된다. 이때 출력은 위치가 낮은 것이 우선이다.

 

풀이:

일단 해당 문제를 풀기 위해서 직접 13이라는 수를 2진수로 변환해보았다. (컴퓨터로 그려서 글씨가 이상한 점은 이해해주길 바란다.)

13을 2로 나눈 몫을 아래에, 나머지를 옆에다가 채워나간다. 이 과정을 13을 2로 나눴을 때 0이 될 때까지 진행한다. 그리고 이진수는 오른쪽에 존재하는 나머지를 아래에서 위쪽으로 읽으면 그것이 10진수를 2진수로 변환한 결과가 된다. 이 과정을 생각하면서 코드를 작성하면 쉽게 작성할 수 있다.

 

아 추가로, 위치가 낮은 순서대로 출력을 하라고 해서 필자의 위 그림처럼 1,1,0,1 이니 0,1,3이 최종 출력되어야 하는 것 아닌가 싶은 분들도 있을 것 같다.그림상으론 그렇지만 따지고보면 맨 위에 있는 1이 가장 먼저 계산된 것이므로 첫번째로 출력되어야 한다. 적은 순서대로 출력한다고 이해하면 될 것 같다.

 

T = int(input())

for i in range(T):
    a = int(input())
    li = []
    result = []

    while a > 0:
        if a % 2 == 1:
            li.append(1)
        else:
            li.append(0)
        a = a // 2

    for index, value in enumerate(li):
        if value == 1:
            result.append(index)
    print(*result)

일단 매우 높은 복잡도를 가지고 있다고 생각해서 당연히 시간초과가 날 줄 알았는데 통과되어서 엥스러웠다.

설명을 하자면 필자는 연산 과정을 거쳐 인덱스값을 저장할 li 리스트와 최종적으로 인덱스가 1인 값만 추려서 출력할 result 리스트를 선언하였다.

그 다음 while문을 돌면서 계속 2로 나눠주는 작업을 진행하였다. 값을 2로 나누면 무조건 0과 1만 존재한다. 그러므로 2로 나눈 나머지가 1일 경우만 생각하면 해당 문제를 풀 수 있다. 나눈 나머지가 1이라면 li 리스트에 1을 추가하고 아니라면 0을 추가한다.

그리고 수기 이진수 변환 설명 부분에서도 말한 것처럼 2로 나눈 몫이 아래로 내려가야하므로 a를 2로 나눈 몫으로 다시 초기화해준다. 그래서 while문이 끝나면 li 리스트에는 [1,1,0,1] 이런식으로 저장이 되어있을 것이다.

우리는 이 리스트에서 1이 저장되어있는 인덱스값이 필요하므로 인덱스와 값을 출력해주는 enumerate 함수를 활용해서 value(값)가 1이면 result 리스트에 해당하는 인덱스를 저장하도록 하고 마지막에 이 result 리스트를 출력해줌으로써 해당 문제를 풀었다!

 

우선 개인적으로 너무 복잡하게 푼 것 같아서 맘에 안드는 코드이긴 하다. 레퍼런스를 좀 더 보면서 효율적인 코드를 찾아봐야겠다.