[백준] 3460번 이진수 (with python)

문제 : 양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 

 

1. 내가 적은 코드 (문제점 다수 존재)

test_case = int(input())
num = int(input())
arr = []
num2 = [0]

while True :
    if (num // 2) != 1 or 0:
        arr.append(num%2)
        num = num//2
    elif (num // 2) == 1 :
        arr.append(num%2)
        num = num//2
        arr.append(num)
        break

for i in range(len(arr)):
    arr.append(arr.pop())

for i in range(len(arr)):
    if arr[i] == 0:
        num2[0] += 1
    else :
        print(num2[0],end=' ')
        num2[0] += 1

내가 풀면서도 '와 이거 개에바다 너무 비효율적인 코드다.'라고 생각했다.

비주얼 스튜디오에서는 주어진 테스트케이스 결과가 잘 출력되었지만

백준은 메모리 초과가 계속 발생하는 상황

 

백준에서 메모리 초과가 발생하는 이유가 

 

1.  너무 많은 변수들을 배열 등에 저장할 경우.

2. DFS 등에서 재귀적 호출을 통해 너무 많은 함수들을 호출할 경우

 

라는데 나는 아마 1번 케이스이지 않을까? 정확하게는 모르겠다. 

 

사람들이 적은 코드를 분석해보자

 

2. 모범 답안(1)

T = int(input())

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

• bin 함수 : 10진수를 2진수로 바꿔줌
  • 변환을 하면 0b11111 과 같은 형식으로 나오기 때문에 숫자만 이용하기 위해 [2:0] 사용
• 역순의 값을 보기 위해서 [-i-1]을 사용하고, 출력은 그대로 i (인덱스의 값)을 출력한다.

 

2. 모범답안(2)

T = int(input())
for _ in range(T):
    n = int(input())
    i = 0
    while n > 0:
        if n % 2 == 1:  # 나머지가 1이면 출력
            print(i, end=' ')
        n = n // 2  # 몫
        i += 1

 

 

 

3. 결론

 

'인덱스의 위치를 어떻게 출력하는 걸까' 에 대해서 많이 고민했는데, 그냥 i에게 +1만 해주면 되는 간단한 문제였다 ㅋㅋ ㅠㅠ