백준 3460 [이진수] : 4가지 풀이 방법과 이진수 구하는 함수 구현하기

📎 Problem

https://www.acmicpc.net/problem/3460

3460번: 이진수

---

📎 Solution

알고리즘 문제 풀이에서 개인적으로 가장 중요하게 생각하는 것은 다양한 방법으로 접근하는 것이다. 한 문제를 풀더라도, 1가지 방안으로 풀이했다고 끝나는 것이 아니라 여러 번의 시도와 고민을 통해 성장할 수 있다. 💪

 

1️⃣ case 1

가장 먼저 풀이한 방법으로 파이썬의 내장함수 bin을 활용하였다. bin 함수를 사용하면 앞에 '0b'라는 문자가 포함된 string 형식으로 리턴되기때문에 index slicing으로 숫자만 짤라주었다. ✂️ python documentation을 참고하여 다양한 방법으로 풀이해보자!

 

bin python documentation

 

 

# case 1 : 메모리 30840KB / 시간 64ms
T = int(input())

# 내장함수인 bin()을 활용하여 이진수로 바꾸는 방법 활용
for _ in range(T):
    # 순서 거꾸로
    bnum = list(reversed(bin(int(input()))[2:]))  # 0b 제거 / string type
    # print(bnum)
    for i in range(len(bnum)):
        if bnum[i] == '1':
            print(i, end = ' ')

 

---

2️⃣ case 2

case1과 비슷한 방법이지만, 이진수의 순서를 거꾸로 변경하지않고, index 번호를 거꾸로 주어 풀이한 방법이다. 시간은 case1이 아주 조금 더 빠르다. 인덱스 번호를 -를 붙여 거꾸로 표현하는 방법은 자주 쓰이니 기억하자! 💡

 

인덱스 번호

 

# case 2 : 메모리 30840KB / 시간 68ms
T = int(input())

# 내장함수인 bin()을 활용하여 이진수로 바꾸는 방법 활용
for _ in range(T):
    bnum = bin(int(input()))[2:]  # 0b 제거 / string type
    for i in range(len(bnum)):
        # 순서 거꾸로
        if bnum[-i -1] == '1':
            print(i, end = ' ')

 

---

3️⃣ case 3

documentation에 언급된 것처럼 bin 함수는 '0b'가 붙어서 출력하기때문에 format이나 f-string을 활용하여 다른 방법으로 풀이할 수 있다.

 

# case 3 : 메모리 29284KB / 시간 52ms
T = int(input())
for _ in range(T):
    # f-string 활용하여 2진수로 바꿔주고 순서 거꾸로
    bnum = f'{int(input()):2b}'[::-1]
    # bnum = format(int(input()), 'b')  # 같은 표현
    # print(bnum)
    G = (b for b in range(len(bnum)) if bnum[b] == '1')  # list comprehension
    print(*G)  #unpacking

 

---

4️⃣ case 4

마지막으로 이진수로 바꾸는 과정을 코드로 구현하여 나머지를 바로 확인하고 출력하는 방법이 있다. 아래 reference에 있는 블로그를 참고하였다.

# case 4 : 메모리 30840KB / 시간 72ms
# 이진수로 바꾸면서 나머지로 바로 확인하고 출력
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

 

---

🔎 cf. 이진수로 만드는 함수 직접 구현

이진수는 2로 더이상 나누어지지 않을 때까지 나누고, 나머지들을 모아서 구할 수 있다. 해당 방법을 코드로 구현하였다.

또한 문제가 index 번호를 출력하는 것이기때문에 enumerate 함수를 활용할 수 도 있다.

 

# cf) 이진수로 만드는 함수 직접 구현
def getBinaryNum(num, result = []):
    a = num // 2
    b = num % 2
    result.append(b)
    if a == 0: return result[::-1]
    else: return getBinaryNum(a, result)

T = int(input())
for _ in range(T):
    bnum = getBinaryNum(int(input()))[::-1]  # 거꾸로
    # print(bnum)
    # enumerate 활용하여 index 번호 프린트하기 & Unpacking
    print(*(i for i, x in enumerate(bnum) if int(x)))  # if int(x) = if 1 = if True

---

📎 Reference

• 풀이 참고 블로그 : https://jinho-study.tistory.com/487
• python bin documentation : https://docs.python.org/3/library/functions.html#bin