[백준 Python] - 2089 -2진수 변환

1. 문제 - 2089번

2. 접근법

-2진법이란 개념에서 고민하다 찾아보니, 처음 생각한대로 원리는 가장 기본적인 진법 변환을 활용한 것이었다.
진법 변환은 나누는 수, 몫, 나머지의 관계애서 출발하므로, 이 문제도 -2를 나누는 수로 하고 나머지를 0 또는 1로 갖는 식으로 계속 나누어 주면 된다.

규칙을 좀더 직관적으로 파악하기 위해, 문제에서 주어진 수 중 9와 -13을 예시로 분석해보았다.

나머지를 반드시 0 또는 1로 만들면서, -2로 계속 나누어 보면 그 과정은 다음과 같다.

-13 = -2*7 + 1
 7 = -2*-3 + 1
-3 = -2*2 + 1
2 = -2*-1 + 0
1 = -1*1 + 1
1 = -2*0 + 1

13 의 결과값 : 1101119 = -2*-4 + 1

-4 = -2*2 + 0
2 = -2*-1 + 0
-1 = -2*1 + 1
1 = -2*0 + 1

9의 결과값 : 11001

여기서 알 수 있는 중요한 점이 있다.
0이 아닌 수를 나누다보면 반드시 최종적으로 몫이 0, 나머지가 1이 된다는 사실이다.

이 점에서 착안해, 아래의 반복문을 작성할 때는 0일 때는 0을 반환하고 반복문을 종료시키는 코드를 넣어주었다.
또한, -2로 나누면 그냥 계산할 때는 나머지가 반드시 -1 또는 0이 나오므로 이 두 경우를 구분해서
나머지가 -1이 나오는 경우 몫에 1을 더해주고 나머지를 1로 처리해주었다.

 <정답 코드>

from sys import stdin, stdout

def dec_to_minbin(decimal):
    minbin = ""

    while True:
        if decimal%-2 != 0:
            minbin = "1" + minbin
            if decimal == 1:
                break
            decimal = decimal//-2 + 1
            
        else:
            minbin = "0" + minbin
            decimal //= -2
            if decimal == 0:
                break

    return minbin

n = int(stdin.readline())

stdout.write(dec_to_minbin(n))

그런데

위에 적은 논리대로 풀었는데도 몇 번을 답을 제출해도 '시간 초과' 가 나왔다.

함수를 없애고 그냥 반복문으로 바꿔보기도 하고, input을 sys.stdin.readline으로 바꾸기도 하는 등 여러 시도를 해봤지만, 시간 초과 문제가 도저히 해결되지 않았다.

구글에서 검색해 원인을 찾아보다 그 이유를 알 수 있었다.

기존의 코드는 함수의 결과 값인 minbin에 반복문 안에서 할당 연산자로 나머지 1 또는 0을 더해주고 출력할 때 인데스 순서를 [::-1]로 뒤집어 주는 것이었다.

그런데 그렇게 할 경우, 처리에 상대적으로 더 시간이 걸린다.
따라서 처음부터 더해줄 때 바르게 출력될 수 있도록 "0" 또는 "1''을 더해주면 되는 것이다.

앞으론 이런 부분은 늘 염두에 두어야 겠다.