입력조건) N은 10,000보다 작거나 같은 자연수이다. 따라서, 브루트포스

# https://www.acmicpc.net/problem/1436
# 영화감독 숌

index = int(input())

count = 0
num = 666

while True:
  if "666" in str(num):
    count += 1
    if count == index:
      print(num)
      break
  num += 1

실패코드1.

💡 아이디어

666 1 
x666 666x -> 9*2 = 18
xx666 x666x 666xx -> (9*9)*3 = 81*3 = 243
xxx666 x666xx xx666x 666xxx -> (9*9*9)*4 -> 2916

규칙: N = (9*m)(m+1)

하지만, 6666이라던가 중복되는 경우의 같은 경우 제외하기 힘듬

#https://www.acmicpc.net/problem/1436
#영화감독 숌

N = int(input())
if N == 1:
    print(666)
else:
    num_x = 1
    sum_len_list = 1
    while sum_len_list < N:
      len_list = (9 ** num_x) * (num_x + 1)
      sum_len_list += len_list
      num_x += 1
    num_x -= 1

    # N이 현재 구간에서 몇번째 인지
    prev_sum = 1
    for i in range(1, num_x):
      prev_sum += (9 ** i) * (i + 1)
    index_in_group = N - prev_sum

    patterns = []
    if num_x == 1:
      for i in range(10):
        patterns.append(int(f"{i}666"))
        patterns.append(int(f"666{i}"))
    elif num_x == 2:
      for i in range(10):
        for j in range(10):
          patterns.append(int(f"{i}{j}666"))
          patterns.append(int(f"{i}666{j}"))
          patterns.append(int(f"666{i}{j}"))
    elif num_x == 3:
      for i in range(10):
        for j in range(10):
          for k in range(10):
            patterns.append(int(f"{i}{j}{k}666"))
            patterns.append(int(f"{i}{j}666{k}"))
            patterns.append(int(f"{i}666{j}{k}"))
            patterns.append(int(f"666{i}{j}{k}"))

    patterns = sorted(set(patterns))  # 중복제거 + 정렬
    print(patterns[index_in_group - 1])

실패코드2. 런타임에러

런타임 오류(Runtime Error) 가 나는 이유는 입력 크기 제한과 루프 범위 때문

💡 아이디어

1부터 10000까지 있는 숫자열에서 666이란 문자열이 포함된 문자추출

나열하여, ${입력숫자 - 1} 이 최종 인덱스

# https://www.acmicpc.net/problem/1436
# 영화감독 숌

index = int(input())

list_have_666 = []
for num in range(666, 10000):   
  if "666" in str(num):
    list_have_666.append(num)

get_num = list_have_666[index-1]
print(get_num)

for num in range(666, 10000):

최대 10,000번째 영화 제목 번호까지 나올 수 있음. 하지만 "666"이 들어간 숫자는 10000까지 돌려서는 충분히 10000개가 나오지 않음.

→ 잘못문제 이해함….

실패코드3. 시간초과

💡 아이디어
666부터 시작해서 num을 증가시켰을 때, 666이 문자열에 들어가 있으면 count 증가 시킴.

count가 입력받은 index와 일치하는 경우, 반복문 break

아니라면, num 계속 증가시키기

# https://www.acmicpc.net/problem/1436
# 영화감독 숌

index = int(input())

count = 0
num = 666

while True:
  if "666" in str(num):
    count += 1
    if count == index:
      print(num)
      break
    num += 1

→ 아이디어는 맞으나 num +=1 들여쓰기 위치 때문

666이 str(num)안에 있으면 무한이 num 증가되기 때문임……그래서 첫 loop부터 무한 증가…