백준 알고리즘 1436 (영화감독 숌) - C++, Python

[문제] 백준 알고리즘 1436 (영화감독 숌)

> https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

 

666부터 6이 연속으로 3번 나오는 N번째 수를 찾는 문제이다.

브루트 포스 문제이고, 떠오른 방법은 2가지이다.

 

1번 풀이 : 숫자 그대로 이용 (C++ 풀이)

1. 숫자 중간이든 끝이든 666이면 되니까, x % 1000을 했을 때 666인지 체크,

    오른쪽의 한 자리씩 없애가며 반복. ( x /= 10 )

2. 만족하는 x를 찾으면, N을 하나씩 줄이며 while문으로 N==0 이면 멈춘다.

 

2번 풀이 : 문자식으로 이용 (Python 풀이)

1. 666부터 str으로 for문을 돌려서 요소가 6이면 cnt += 1 해주고,

    연속 3개가 아니면 다시 cnt = 0

2. 만족하는 x를 찾으면, N을 하나씩 줄이며 while문으로 N==0 이면 멈춘다.

 

최대한 효율적이게 짰는데도, Python으로는 걸리는 시간이 무지막지하다.

Python은 1번 풀이, 2번 풀이로 어떻게 돌려도 둘 다 느리다......

Python3로는 C++보다 70배 이상, Pypy3로 해도 10배 느림.

 

[C++]

#include <cstdio>
using namespace std;

int solve(int n) {
	int out = 0, tmp_i = 0, i = 666;
	while (n != 0){
		bool flag = 0;
		tmp_i = i;
		while (tmp_i != 0) {
			int mod = 0;
			mod = tmp_i % 1000;
			tmp_i /= 10;
			if (mod == 666) {
				out = i;
				n--;
				break;
			}
		}
		i++;
	}
	return out;
}

int main() {
	int n = 0;
	scanf("%d", &n);
	printf("%d", solve(n));
}

 

[Python]

import sys
N = int(sys.stdin.readline())
num = 666
while N != 0:
    flag = False
    cnt = 0
    for i in str(num):
        if i == '6':
            cnt += 1
        elif cnt < 3:
            cnt = 0
    if cnt >= 3:
        out = num
        N -= 1
    num += 1
print(out)