백준 1681번: 줄 세우기
문제 설명
- 한자리 숫자 L을 사용하지 않고 1부터 시작하는 N개의 숫자를 만들어야 합니다.
접근법
- 반복문을 사용해야 합니다.
- 언제 N번째 숫자가 등장할 지 모르기 때문에
for
문이 아닌while
문을 사용합니다.
- 언제 N번째 숫자가 등장할 지 모르기 때문에
- 긴 숫자(N)에 짧은 숫자(L)가 포함되는지 판단하기 위해서는
문자열
로 바꾼 뒤in
기능을 활용해야 합니다.
정답
N,l = list(map(int,input().split(' ')))
num = 1 # 양의 정수이기 때문에 0이 아닌 1부터 시작합니다
cnt = 0 # 라벨을 붙인 개수
while True:
if str(l) not in str(num): #해당 숫자를 사용할 수 있으면
cnt+=1 #라벨을 붙입니다
if cnt == N: #N개의 원소를 다 라벨링했다면
print(num) #마지막 값을 출력하고
break #반복문을 그만둡니다
num+=1 #반복문이 끝나지 않았다면 다음 숫자로 넘어갑니다
else: #l이 포함되어 해당 숫자를 사용할 수 없다면
num+=1 #다음 숫자로 넘어갑니다
기타
- 시간초과가 났다면?
- N = 1,000,000이고 L = 1일 때 2,894,772의 결과값이 나온다. 이는 프로그램을 돌려서 구한 숫자일 뿐 나는 문제 조건만으로 시간복잡도를 유추하지 못했다(계산 가능하신분은 댓글 부탁드립니다)
- 시간초과가 발생했다면 선형탐색을 포기해야 하는데 이외에 어떤 방법이 가능한지 잘 모르겠다 (아시는분은 댓글 부탁드립니다)
Author And Source
이 문제에 관하여(백준 1681번: 줄 세우기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-1681번-줄-세우기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)