[baekjoon] 백준 1323번(파이썬): 숫자 연결하기

문제

1323번: 숫자 연결하기

알고리즘

- 나머지 연산을 하고 나머지가 0인지 확인한다.

- 나머지가 0이면 연산 횟수를 출력한다.

- 0이 아니라면 str으로 같은 수를 더하는 연산을 한다.

- set() 자료형에 나누어야 하는 수를 추가하고 나누어야 하는 수가 set() 집합에 포함되어 있으면 무한 루트 이므로 -1을 출력한다.

코드

import sys

n, k = map(str, sys.stdin.readline().split())
cnt = 0 # 연산 횟수
temp = n # 같은 수를 더하는 연산을 해줄 변수
paper = set() # set() 자료형이 list() 자료형보다 더 빠른 거 같다?..

# 반복문을 통해 n을 몇 번 써야 k로 나누어 떨어지는지 확인
while True:
    temp = int(temp) % int(k) # 나누기 연산
    cnt += 1 # 카운트
    
    # 나머지가 0이면 나누어 떨이진 것
    if temp == 0:
        break

    else:
        # 같은 수를 더하는 연산
        temp = str(temp) + str(n)
        
        # 나누어야 하는 수가 집합에 포함되어 있으면
        # 무한 루트이므로 -1 출력
        if temp in paper:
            cnt = -1
            break

        # 나머지 리스트 집합에 나누어야 하는 수를 추가
        paper.add(temp)

print(cnt)

 

실패한 코드(시간 초과)

import sys

n, k = map(str, sys.stdin.readline().split())
cnt = 0 # 연산 횟수
temp = n # 같은 수를 더하는 연산을 해줄 변수
paper = []

# 반복문을 통해 n을 몇 번 써야 k로 나누어 떨어지는지 확인
while True:
    temp = int(temp) % int(k)
    cnt += 1
    if temp == 0:
        break
    else:
        temp = str(temp) + str(n)

        if temp in paper:
            cnt = -1
            break
        paper.append(temp)

print(cnt)

나누어야 하는 수를 저장하는 공간을 list() 자료형으로로 하면 시간 초과가 나오고 set() 자료형으로 하면 통과되는 것을 봤을 때 set() 자료형이 list() 자료형보다 시간 복잡도? 가 더 빠른 거 같다. 그래도 자세한 것은 더 공부해봐야 할 거 같다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법