[파이썬/Python] 백준 1436번 영화감독 숌

[파이썬/Python] 백준 1436번 영화감독 숌

1436번: 영화감독 숌

---

문제

666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

 

해설

예제 입력 부분을 조금만 훑어봤다면 단순히 숫자 붙이기라고 생각할 수 있다.

그러나, 예제 입력이 7이라면 결과는 6666이 아니라 6660 이다.

즉, '666'이 포함되는 가장 작은 숫자를 순서대로 출력해야한다.

 

1. 모든 숫자를 탐색한다.

2. 666이 포함되는 숫자를 오름차순으로 저장한다.

 

코드

import sys
lst = []

for i in range(10000000):
    if '666' in str(i):
        lst.append(i)

print(lst[int(sys.stdin.readline())-1])

 

풀이

for i in range(10000000):
    if '666' in str(i):
        lst.append(i)

1. 적당한 범위를 정한 후에, 반복문을 통해 '666'이 포함된다면 리스트에 저장한다.

정수형은 문자열이 포함되어 있는지 여부를 확인할 수 없기 때문에 문자열로 형변환을 해야한다.

 

print(lst[int(sys.stdin.readline())-1])

2. 입력 받은 값에 따라 배열의 해당 인덱스의 값을 출력한다.

 

피드백

내가 처음 접근했던 방법으로 코드를 동작시키게 된다면, 범위를 지정해주는 것이 모호할 뿐만 아니라 해당 값들을 전부 탐색하면서 그 값을 형변환 해주고 그 안에서 값을 비교하는 매우 비효율적인 과정을 거친다.

 

내가 풀면서도 매우 찝찝했다.

 

그래서, 최대한 탐색을 줄일 수 있는 방법, 더 효율적인 접근방법에는 무엇이 있을까 찾아보았다.

 

import sys

n = int(sys.stdin.readline())
i = 666
cnt = 0

while 1:
    if '666' in str(i):
        cnt += 1
    if cnt == n:
        print(i)
        break
    i += 1

대부분의 사람들이 위 방식으로 문제를 해결했다.

 

규칙성과 인과관계 등을 따져보지 않고, 모든 경우에서 가장 효율적인 방법인듯 하다.

 

내가 작성한 코드처럼 1~1000000 범위의 숫자를 모두 비교하는게 아니라,

666을 시작지점으로 하여 사용자가 입력하는 인덱스까지 만큼만 탐색을 진행한다.

 

동작시간 또한 현저히 줄어든 모습을 확인할 수 있다.

 

그렇다면 666을 포함한 가장 작은 숫자의 규칙성을 찾은 방법은 어떨까?

 

import sys

def how(n):
  if n%10==6: return 10*how(n//10)
  else: return 1

def getRes(first, mid, last, lst):
  print(first * 1000 * lst + mid * lst + last)
  sys.exit(0)

N = int(input())
first, mid, last, cnt = 0, 666, 0, 0

while cnt<N:
  idx = how(first)
  if idx > 1:
    for i in range(0, idx):
      cnt += 1
      if cnt == N:
        getRes(first // idx, mid, last, idx)
      last += 1
    last = 0
  else:
    cnt += 1
    if cnt == N:
      getRes(first, mid, last, idx)
  first += 1

문제의 규칙에 따라, 숫자는 666 사이에 앞과 뒤에 생겨날 것이고, 가장 작은수부터이기 때문에

앞자리부터 1,2,3 .. 순으로 생성된다. 

 

여기서 변수가 되는 부분은 앞자리가 6일 때, 뒷자리에 숫자가 추가되는게 더 작다는 것이다.

 

위 코드는 이 부분을 how 함수를 통해 캐치한다.

 

간단한 증감연산자만으로 문자열의 비교없이 문제를 풀어낸다.

 

작동시간에 매우 예민한 프로그램이라면 이러한 디테일한 부분까지 신경써야된다고 느꼈다.

 

참고자료

[백준] 1436번(python 파이썬)

로그인