자바 - 백준 - 1436번 영화감독 숌

나에게는 아직 어려운 실버 문제. 그렇지만 기록을 남기지 않으면 또 까먹을 나를 알기에, 또 누군가에게는 도움이 되었으면 하는 바람으로 글을 남긴다.

 

백준의 1436번 문제, 영화감독 숌의 힌트를 주자면 해당 문제는 브루트포스 알고리즘 이다.

온갖 경우의 수를 알아보는 브루트포스의 이번 문제는 다음과 같다.

 

 

이 문제를 보았을 때, 브루트포스니까 무식하게 접근해야지라는 아주 어리석은 태도를 가졌었는데 OH NO, 시간만 버렸다.

 

처음 나의 접근방법은 666이 카운팅 되는 패턴이 있을 것이라고 판단하여 액셀을... 사용했다. 오로지 패턴을 알기 위해..!

그렇게 무식한 나의 접근방법은 30분이라는 귀중한 시간을 허비하게 만들었고, 정신 차리고 다른 해법을 고민하기 시작했다.

고민은 했으나 답은 나오지 않았다. 힌트를 찾아보았다.

 

힌트 1 : 666을 문자열로 만들기

힌트 2 : 만든 문자열을 카운팅 하기

 

🫥 그렇게 해서 만든 첫 코드

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 num = 666;
        String str = Integer.toString(num);
        int cnt = 0;

        // 찾으면 ++,
        while(true) {
            if(str.contains("666")){
                cnt++;
            }
            if(cnt==n){
                System.out.println(num);
                break;
            }
            num++;
            str = String.valueOf(num);
        }

    }
}

사실 참고한 블로그의 코드와 너무 같아서 개발자가 아니라 코더가 된 느낌이었다. 풀기에만 급급해하다 보니 약간의 부끄러움이 있다.

해당 코드가 직관적으로 봤을 때 매우 이해가 잘 되었으나 아쉬운 점은 메모리 용량을 많이 차지한다는 부분이었다.

다른 사람은 어떻게 풀었는지 궁금해졌다.

 

🥸 다른 사람의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int num = 666;
		int cnt = 0;

		for (int i = 666; cnt < N; i++) {
			if (isAnswer(i)) {
				cnt++;
				if (cnt == N) {
					num = i;
				}
			}
		}
		System.out.println(num);
	}
	public static boolean isAnswer(int N) {
		int a = N;
		int b = N % 1000;

		while (a > 665) {
			if (b == 666) {
				return true;
			} else {
				a /= 10;
				b = a % 1000;
			}
		}
		return false;
	}
}

위 풀이는 for문을 돌려서 %1000 나머지 연산자로 666의 숫자를 찾고 그것을 카운팅 한 횟수가 n과 동일할 때 값을 구하는 방법을 선택하였다.

boolean 값을 이용하여 간단한 함수를 구현하는 방법을 연습해 봐야겠다. 

 

참고 블로그 

[백준] 1436번 : 영화감독 숌