[CodeUp] 2102번 : 배수 (Hard) (Python)

Python

방법 1 - 메모리 88796 / 시간 486 / 코드 길이 302B

본 문제를 이해하고 몇 번 끄적이다보니 BFS를 활용하는 문제임을 간파하였다.

이 문제의 특징은 자연수로 이뤄진 0과 1의 조합을 보는 것이다.

즉, 1부터 시작해서

10, 11

100, 101, 110, 111

1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

이런 식으로 가로 queue에 넣어 순차적으로 보는 것이다.

이를 위한 BFS를 구성해야하고 이 때의 queue를 위해서는 collection에서 deque를 불러와서 사용한다.

또한 unsigned long long형의 범위를 넘어서면 0이되어야 하므로 해당 범주를 설정하기 위한 if문을 설정해야한다.

이 때 unsigned long은 4바이트이고 unsinged long long은 8바이트이다.

즉, $2^{64}$가 넘어서면 0을 반환하도록 설정한다.

만약 숫자가 초기 받는 값에 떨어지면 그 값을 반환하면 되지만 그렇지 않다면 queue에 계속 값을 넣어가며 queue의 list를 늘려간다.

ex)

396을 넣었을 때 11111111111111111100 반환

1048576을 넣었을 때 0 반환

다만 생각보다 많은 메모리와 시간을 소모하는 것이 단점이다.

from collections import deque

def bfs(n, s):
  queue = deque([s])
  
  while queue:
    t = queue.popleft()
    
    if t >= 2**64:
      return 0      
    elif t % n == 0:
      return t   
      
    queue.append(t*10)
    queue.append(t*10+1)

n = int(input())
print(bfs(n, 1))

방법 2 - 메모리 27724 / 시간 538 / 코드 길이 274B

BFS 외의 방식으로 풀는 방법은 다음과 같은 방법이 있다.

본 형태를 잘 살펴보면 2진법과 같은 0과 1로만 구성된 것을 확인할 수 있다.

즉, binary를 잘 이용하면 이를 조금 더 쉽게 풀 수 있을 것으로 판단하였다.

0b는 binary이고 이후의 숫자가 바로 그 값이 된다.

0b1 = 1

0b11 = 3

0b111 = 7

그러나

format으로 형태를 잡고 10진법으로 바꾸게 되면 0b1을 10진법의 1로 활용할 수 있고 0b11을 10진법의 11로 활용할 수 있다.

유의!

def seq(n) : 
    bi = 0b1
    deci = int(format(bi, "b"), 10)

    while(1): 
      if deci >= 2**64 : 
        return 0
      elif deci % n == 0 : 
        return deci  
      bi += 1
      deci = int(format(bi, "b"), 10)
      
n = int(input())
print(seq(n))