백준 1681번: 줄 세우기

문제 설명

• 한자리 숫자 L을 사용하지 않고 1부터 시작하는 N개의 숫자를 만들어야 합니다.

접근법

• 반복문을 사용해야 합니다.
  • 언제 N번째 숫자가 등장할 지 모르기 때문에 for문이 아닌 while문을 사용합니다.
• 긴 숫자(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의 결과값이 나온다. 이는 프로그램을 돌려서 구한 숫자일 뿐 나는 문제 조건만으로 시간복잡도를 유추하지 못했다(계산 가능하신분은 댓글 부탁드립니다)
  • 시간초과가 발생했다면 선형탐색을 포기해야 하는데 이외에 어떤 방법이 가능한지 잘 모르겠다 (아시는분은 댓글 부탁드립니다)