[좌충우돌, 파이썬으로 자료구조 구현하기] 큐를 이용하여 이진수 만들기

문제

자연수 N이 주어졌을 때, 1부터 N까지의 이진수를 순서대로 출력하는 함수를 구현해라

풀이

1. 내장함수 이용

def generate_binary(n):
    for i in range(1, n+1):
        print(bin(i)[2:]) # 이진수에 0b가 붙으므로 슬라이싱으로 제거

• bin() 내장함수는 정수형을 이진수 문자열로 반환한다.

문제 분석하기

>>> generate_binary(5)
1  
10  
11  
100  
101

• 2의 이진수와 3의 이진수는 1의 이진수에 0, 1을 붙인 것이다.
• 4의 이진수와 5의 이진수는 2의 이진수에 0, 1을 붙인 것이다...

그렇다면, 6과 7의 이진수는 3의 이진수에 0과 1을 붙인 것으로 예상할 수 있다.

앞서 사용한 이진수에 0과 1을 붙인 이진수가 나중에 사용된다. 그러므로 큐에서 이진수를 꺼내어 출력하고 해당 이진수에 0과 1을 붙인 이진수를 큐에 추가한다.

2. 큐를 이용하여 풀기

def solution(n):
    queue = ['1']
    for _ in range(n):
        popped = queue.pop()
        queue.insert(0,popped+'0')
        queue.insert(0,popped+'1')
        print(popped)

• queue 리스트의 1번째 요소를 1을 이진수로 나타낸 '1'로 채워준다.
• queue는 선입선출이므로 앞에서부터 추가(enqueue)하고, pop으로 마지막 요소(dequeue)를 제거하여 출력한다.