백준 1436번 : 영화감독 숌

처음에는 이 문제를 단순하게 브루트포스로 풀었다.

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());
        int answer = 0;
        int i = 666;
        while (answer < n) {
            if (String.valueOf(i).contains("666")) {
                answer++;
            }
            i++;
        }
        System.out.println(i-1);
    }
}

그런데, 검색을 해보니 메모리와 시간을 줄이는 최적화 방법이 있어서 참고하여 다시 풀어봤다.
참고: https://st-lab.tistory.com/103
위 블로그에 정리가 잘 되어있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());

        if (n == 1) {
            System.out.println("666");
        }
        int answer = 1;
        int prevDigit = 0;
        int num = 0;

        while (n > 1) {
            // 10000번째 수가 3000000을 넘지 않으므로..
            // 1000666 ~ 2xxx666~ 까지 prevDigit를 1씩 증가시키는데, 1666000~ 1666999 포함돼있으므로 끝자리가 6인것 제외
            if (prevDigit % 10000 / 10 == 666 && prevDigit % 10 != 6) {
                for (int i = 0; i < 1000; i++) {
                    if (answer == n) {
                        System.out.println(prevDigit + "" + num);
                        return;
                    }
                    answer++;
                    num++;
                }
                prevDigit++;
            }
            else if (prevDigit % 1000 == 666) {
                num = 0;
                for (int i = 0; i < 1000; i++) {
                    if (answer == n) {
                        System.out.println(prevDigit + "" + num);
                        return;
                    }
                    answer++;
                    num++;
                }
                prevDigit++;
            }
            else if (prevDigit % 100 == 66) {
                num = 600;
                for (int i = 0; i < 100; i++) {
                    if (answer == n) {
                        System.out.println(prevDigit + "" + num);
                        return;
                    }
                    answer++;
                    num++;
                }
                prevDigit++;
            }
            else if (prevDigit % 10 == 6) {
                num = 660;
                for (int i = 0; i < 10; i++) {
                    if (answer == n) {
                        System.out.println(prevDigit + "" + num);
                        return;
                    }
                    answer++;
                    num++;
                }
                prevDigit++;
            }
            else {
                num = 666;
                if (answer == n) {
                    System.out.println(prevDigit + "" + num);
                    return;
                }
                answer++;
                prevDigit++;
            }
        }
    }
}

위같은 식으로 나혼자 풀라고 하면 백날이 걸려도 못 풀었을 것 같다.