[BOJ] 3460. 이진수

3460번: 이진수

 

✍️ 문제 요약

양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치(인덱스)를 모두 출력하라.

 

💪 무식하게 풀기

문제를 읽자마자 생각나는대로 흐름을 정리해 보았다.

1. n을 2로 나눈 몫을 문자열에 누적한다.

2. n을 나머지로 갱신하며 마지막에 n을 누적한다. 

3. 만들어진 문자열을 순환하며 1인 요소의 인덱스를 출력한다.

def getBinary(n):
    res = ''
    while n >= 2:
        res += str(n%2) # 맨 뒤에 누적 (결과는 거꾸로)
        n //= 2
    res += str(n)
    return res 

TC = int(input())

for _ in range(TC):
    N = int(input())
    for i, x in enumerate(getBinary(N)):
        if x == '1':
            print(i, end=' ')

시간 복잡도는 

 

🎯 최적화

TC = int(input())

for _ in range(TC):
    binary = bin(int(input()))[2:] # 0b 제외
    for i, x in enumerate(binary[::-1]): # 거꾸로
        if x == '1':
            print(i, end=' ')

시간 복잡도는

 

🤔 다른 사람의 코드를 탐구해보기

2진수의 값을 역순을 봐야 하기 때문에 [-i-1]를 사용하여 역순으로 한 문자열씩 보기 시작한다.

TC = int(input())

for _ in range(TC):
    binary = bin(int(input()))[2:]
    for i in range(len(binary)):
        if binary[-i-1] == '1': 
        	print(i, end=' ')

 

📚 참고 자료

https://seungyong20.tistory.com/7