[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번째 영화의 제목에 들어간 수를 출력한다.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // N 입력

        int num = 666; // 시작 종말의 수
        int count = 0; // 종말의 수 개수 카운트

        while (true) {
            // num에 6이 연속으로 3번 이상 나타나는지 확인
            if (hasThreeConsecutiveSixes(num)) {
                count++; // 종말의 수 개수 증가
            }

            if (count == N) {
                System.out.println(num);
                break;
            }

            num++; // 다음 수로 이동
        }
    }

    // num에 6이 연속으로 3번 이상 나타나는지 확인하는 함수
    public static boolean hasThreeConsecutiveSixes(int num) {
        String numStr = String.valueOf(num);
        return numStr.contains("666");
    }
}

---

여기서 사용된 알고리즘은, "브루트포스" 알고리즘이다.

 

브루트 포스(Brute Force) 알고리즘은 컴퓨터 알고리즘 중 가장 직관적이고 간단한 방법 중 하나입니다. 이 방법은 가능한 모든 경우의 수를 모두 시도해 보는 것으로, 답을 찾는 알고리즘입니다. 브루트 포스 알고리즘은 특히 문제의 크기가 작을 때나 답을 찾는 방법을 명확히 알 수 없을 때 유용하게 사용됩니다.

브루트 포스 알고리즘의 절차는 다음과 같습니다:

1. 가능한 모든 경우의 수를 나열한다.
2. 각 경우에 대해 문제의 조건을 만족하는지 확인한다.
3. 조건을 만족하는 경우 결과를 기록하거나 반환한다.

브루트 포스 알고리즘의 장점:

• 문제를 직관적으로 접근할 수 있다.
• 모든 가능한 경우를 시도하기 때문에 정확한 답을 찾을 수 있다.

브루트 포스 알고리즘의 단점:

• 경우의 수가 많을 경우에는 계산이 매우 느려질 수 있다.
• 문제의 크기가 커질수록 비효율적이다.

브루트 포스 알고리즘은 주로 작은 입력 크기에 적용되거나, 최적화된 알고리즘이 없는 경우에 사용됩니다. 문제의 특성에 따라 브루트 포스 알고리즘이 가장 적합한 경우도 있고, 더 효율적인 알고리즘이 필요한 경우도 있습니다.