[백준] 영화감독 숌 (Python)

✏️ 문제

1436번: 영화감독 숌

✏️ 풀이

666이 들어가는 N번째 수를 구하는 문제이다.

1666, 2666, 3666, 4666, 5666, 6661,,, 6666,,,7666,, 

이렇게 666 앞에 들어가는 수가 6으로 끝날 경우 위와 같이 규칙이 달라지므로 따로 처리해줘야한다.

예를 들어, 15666에서 16666으로 넘어갈 때 6으로 끝나므로

15666

16661

16662

기존의 6을 떼주고 666뒤에는 1부터 9까지 붙여준다.

56669

66601

...

66699

이와 같이 6의 길이가 두자리이면 1부터 99까지 두자리를 유지하며 붙여줘야한다.

아래는 이를 구현한 코드이다.

✏️ 코드

def six_range(arr):
    count = 0
    for six in arr[::-1]:
        if six != '6':
            break
        count += 1
    return count


n = int(input())
if n==1:
    print('666')
else:
    x = 1
    cnt = 1
    while True:
        length = six_range(str(x))
        if length > 0:
            for i in range(pow(10,length)):
                ans = str(x)[:len(str(x))-length] + '666' + str(i).zfill(length)
                cnt += 1
                if cnt==n:
                    break
        else:
            ans = str(x) + '666'
            cnt += 1
        if cnt==n:
            break
        x += 1

    print(ans)

매우.. 복잡하다..ㅎ

✏️ 다른 사람 풀이

N = int(input())
movie = 666

while N:
    if "666" in str(movie):
        N -= 1
    movie += 1

print(movie - 1)

브루트포스로 풀이한 코드이다.

666부터 차례대로 증가시키면서 666을 포함한 숫자를 n번 만날 때까지 실행한다.

 

✏️ 생각

너무 복잡하게 풀었나 생각....

풀이 자체는 엄청엄청 복잡하지만.. 시간 복잡도는 차이가 크게 나긴 한다.

그치만 풀이가 복잡하다보니 규칙 알아내고 구현하는데 시간이 너무 많이 걸린다는 점.. 

N을 10000을 넣었을 때 답이 2666799이기 때문에

결론적으로는 브루트 포스 알고리즘을 쓰는 편이 구현 시간 면에서는 훨씬 좋은 선택이었다는.. 결론...또륵

코테때는 브루트 포스로 한 번 시도해보고 시간 초과되면 다른 규칙을 찾는 것이 좋을 것 같다!