티스토리 뷰

❗ 결론: 파이썬에서 문자 포함 여부를 확인하기 위해서는 in 오퍼레이터를 사용할 것!

[문제]

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.
하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.
종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다.
따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.
숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

 간략히 하자면, 입력값으로 정수 하나(N)가 들어오는데, 666을 포함하는 수를 오름차순 정렬을 했을때 앞에서부터 N번째에 위치하게 되는 수를 출력하는 프로그램을 작성하면 된다.

 

 

[내 코드]

N = int(input())

i=666; order = 1
while(order != N):
    i+=1
    if str(i).find("666") != -1:
        order+=1
print(i)

 브루트포스 알고리즘으로 간단히 작성할 수 있었다. 종말의 수 중에서 앞에서부터 몇번째인지를 저장하는 order가 입력값으로 들어온 N과 같아지기 전까지 첫 종말의 수인 666부터 1씩 더해가며, 해당 수가 666을 포함하는 지를 확인하고 포함한다면 order의 수를 1씩 더해준다.

 

 이 단순한 알고리즘 속에서 내가 집중한 것은 성능(실행시간)이었다. 나와 단 한줄의 차이로 실행시간을 줄이신 다른 분이 계시길래, 코드를 참고해보니 문자열 포함 판별 조건에서 find가 아닌 in 오퍼레이터를 사용한 결과였다.

 스택오버플로우에서 발견한 글에 따르면, 해당 문자열이 특정 문자를 포함한다는 가정하에서

in > __contains__ > find >  index 의 순으로 빠르게 작동하며, 

__contains__in의 동작 과정을 disassemble 한 결과 in이 더 간단한 과정을 거친다는 것도 알 수 있었다.

그 외의 수많은 댓글들이 문자열 포함 판별에서 __contains__, find, index보다는 in 오퍼레이터를 사용할 것을 권하고 있었다. 주로 다른 언어에서는 주로 contains를 사용하다보니 헷갈릴 수 있지만, python에서는 in 오퍼레이터를 사용할 것!

 

 

[코드 수정 후 성능의 변화]

이 작은 차이들이 쌓이면 분명 엄청난 성능 차이를 보일 것이다. 사소한 것부터 잡아가자!

 

 

[참고]

https://stackoverflow.com/questions/3437059/does-python-have-a-string-contains-substring-method

 

문제 풀러 바로 가기 >>

Comments