[Java][자바][백준][1436번] 영화감독 슘

문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

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

입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

 

생각

처음엔 규칙을 찾으려고 했다. 666 1666 2666 증가하다가 5666 다음에는 6660 6661 ... 6669 이런 방식으로 증가할 것이다. 하지만 한참을 들여다봐도 규칙을 찾을 수 없었고, 결국 숫자를 증가시키며 666을 포함하고 있으면 하나씩 넣는 방식을 하기로 했다. N의 범위가 10000까지다 보니, 숫자는 꽤 커질 것이고 최대한 효율적으로 생각하기로 했다.

 

처음에 사용한 방법은 숫자를 String형으로 바꾸고 666을 포함하고 있으면 count를 추가시켜 count가 N이 되면 while문을 나오게 하였다. 코드는 짧았지만 시간이 388ms가 나오고 메모리가 생각보다 많이 나왔다. 내가 사용한 contains가 결국 처음부터 찾는 것이기 때문에 메모리가 많이 먹은 것 일까..? 그래서 String을 만들지 않고 다른 방법을 사용하기로 했다.

 

10으로 나눈 나머지를 구하면서 6을 포함하면 count를 증가시키고 아니면 count를 0으로 만든다. (연속해서 나오는 것을 표현하기 위해) 이 count가 3이 되면 666을 포함하는 숫자인 것이다. 

 

코드

- 첫 번째 방법

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int start = 666;
        int count = 0;
        
        while(count != n) {
            String str = "" + start;
            
            if(str.contains("666")) {
                count++;
            }
            
            start++;
        }
        
        System.out.println(start - 1);
    }
 
}

- 두 번째 방법

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int start = 666;
        int count = 0;
        
        while(count != n) {            
            if(check666(start)) {
                count++;
            }
            start++;
        }
        
        System.out.println(start - 1);
    }
    
    static boolean check666(int n) {
        int count = 0;
        
        while(count!=3) {
            int k = n%10;
            
            if(k==6) {
                count++;
            } else {
                count = 0;
            }
            
            n = n/10;
            if(n==0) break;
        }
        
        if(count == 3) {
            return true;
        } else {
            return false;
        }
    }
}
 

두 번째 방법이 시간도 150ms가 나오고 메모리도 훨씬 적게 소비됬다 !