[백준] 1436번 : 영화감독 숌 - JAVA [자바]

www.acmicpc.net/problem/1436

1436번: 영화감독 숌

 

---

• 문제

 

 

 

매우 간단한 문제지만 예외의 상황을 잘 고려해야 하는 문제다.

 

---

• 알고리즘 [접근 방법]

 

이 문제의 경우 브루트포스를 사용할 수도, 사용하지 않을 수도 있는 문제다.

두 가지 접근법을 살펴보도록 하자.

 

 

 

 

[방법 1]

 

일단 N 번째 ( 1 ≤ N ≤ 10000 ) 로 큰 "666" 이 들어가는 수를 찾아야 한다.

 

가장 간단하게 브루트포스를 사용하는 방법은 N 의 최솟값은 1 이니 결국 666부터 시작하여, 1 씩 증가하여, 해당 문자열에 666이 담겨 있을 경우 count 를 1씩 증가시키고, N 이 count 랑 같아지면 해당 숫자를 출력하면 되는 것이다.

 

이때 숫자를 증가시킬 때는 int 형으로, 666이 포함되는지를 검사할 때는 문자열로 검사하는게 좋다.

 

문자열 검사 방법은 chatAt() 을 통해 검사하는 방법도 있지만, contains() 메소드를 사용하는 방법도 있다. contain 메소드는 해당 문자열 안에 검사하려는 문자열이 포함이 되어있는지를 검사하고, 검사하려는 문자열이 담겨있으면 true, 없으면 false 를 반환한다.

 

즉, 간단하게 알고리즘을 구상하자면 다음과 같다.

 

int N = input(); // 입력

int num = 666;
int count = 1;

while(count != N) {
	num++;
    
	// int형인 num을 String으로 변환한 뒤, "666"이란 문자열이 있는지 검사
	if(String.valueOf(num).contains("666")) { 
		count++;
	}
}
print(num);

 

즉, 666 부터 시작하여 1씩 증가시켜 해당 값이 666 을 포함하고 있다면 count값을 증가시킨다. 그리고 count 값이 N 이랑 같아질 경우 해당 num 이 N번째 숫자가 되는 것이다.

 

 

 

 

 

[방법 2]

 

위 방법도 좋지만 666부터 count 가 같아질 때까지 모든 수를 검사해야한다는 것은 어쩌고보면 매우 비효율적일 수 있다.

그러면 더 좋은 방법은 무엇일까?

 

가장 효과적인 방법은 구간을 나누어서 count 를 하는 것이다.

 

일단 N 번째의 수를 쭉 나열해보자.

666, 1666, 2666, 3666, 4666, 5666, 6660, 6661, 6662, ⋯, 6669, 7666, 8666, 9666, ⋯

 

바로 위에 볼드처리한 부분이 키포인트다. 5666 다음 6666이 아니라 6660 부터 시작해야한다. 

 

5자릿수도 마찬가지다.

10666, 11666, 12666, 13666, 14666, 15666, 16660, 16661, 16662, ⋯, 16669, 17666, ⋯

즉, 5자리 수에서도 4자수의 구간을 똑같이 반복하는 식이다.

 

다만 5자릿수의경우는 경우의 수가 더 추가된다. 바로 5번째 자릿수가 6일 경우, 즉 아래와 같을경우도 생각해야한다.

60666, 61666, 62666, 63666, 64666, 65666, 66600, 66601, ⋯, 66659, 66660, ⋯

 

 

즉, 우리는 666인 구간만 찾아서 위의 경우의 수를 생각하여 각 자릿수 값만 증가시키면 된다.

(참고로 해당 문제에서 N 이 10000 일 때 결과값은 2666799 이다. 그러므로 최대 7자릿수까지의 경우의 수만 체크해보도록 하자.

 

 

알고리즘은 다음과 같다.

첫 번째가 666 이고, 두 번째는 1666 이다.

 

이때 1 을 prev_digit (가장 선수에 있는 자릿수) 라고 하고, prev_digit 을 증가시키면서 count를 센다.

그러다가 prev_digit 이 6이 될 경우 6660 이라고 가정하여 따로 반복문에 0~9 까지 count 를 증가시킨다. 해당 반복문이 종료되면 다시 prev_digit 을 증가시킨다.

그 다음에는 prev_digit이 66 일경우 위와 같이 하되, 0~100까지 반복하면서 count를 돌려준다.

위 과정중에 N 이 count 랑 같아지면 prev_digit 뒤에 나머지 수를 붙여 출력하면 된다.

 

이런식으로 prev_digit 의 경우에 따라 조건문을 달아 반복하면 된다.

 

말로 설명하긴 어려우니... 아래 풀이(방법 3, 방법 4) 코드에서 확인해보자.

 

 

 

 

 

 

 

 

---

• 4가지 방법을 이용하여 풀이한다.

 

필자가 앞서 알고리즘에서 말했던 두 가지 방법을 이용할 것이다.

다만 각 방법에 각기 다른 입력방법을 이용하여 성능의 차이를 같이 보고자 한다.

 

입력은 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이다.

 

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();

		int num = 666;
		int count = 1;
        
		while(count != N) {
			num++;
			if(String.valueOf(num).contains("666")) {
				count++;
			}
		}
		System.out.println(num);
	}
}

 

 

브루트포스를 사용한 가장 기본적인 방법이다.

 

해당 알고리즘은 누구나 쉽게 풀 수 있는 알고리즘이라 따로 설명할 필요는 없을 것 같다. 그저 입력받은 N과 count 가 같아질 때 까지 num을 1씩 증가시켜 666이 포함되는지 여부를 계속 검사하는 것이다. 물론 효율로 보면 매우 뒤 떨어지는 성능이긴 하지만, 쉽게 접근할 수 있는 방법이라 대개 이와같이 풀지 않았을까 생각된다.

 

 

---

- 방법 2 

 

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

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;
		int count = 1;
        
		while(count != N) {
			num++;
			if(String.valueOf(num).contains("666")) {
				count++;
			}
		}
		System.out.println(num);
	}
}

 

 

방법 1에서 Scanner 대신 BufferedReader 을 사용하여 입력받는 방식이다. 알고리즘 자체는 동일하니 크게 어려운 점은 없을 것이다.

 

---

- 방법 3 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
        
		int N = in.nextInt();	

		if (N > 1) {
			func(N);
		} 
		else {
			System.out.println(666);
		}
	}

	public static void func(int n) {
		int count = 1;
		int prev_digit = 0; // 선수 자릿수
		int num = 0;		// 선수 자릿수를 제외한 나머지 뒷 자릿수
		
		/*
		 
		   설명 표현 방법
		   '_'(언더바)를 기준으로 표현한다.  ex) (prev_digit) _ num
		   이 때, 자릿수에 따라서 num 은 0 또는 600, 660, 666 을 갖는다.
		   
		 */
		while (true) {

			/*
			 *  선수 자릿수가 X...666X 이면서 X...6666 이 아닐 경우 
			 *  (ex. 6660_000, 6660_001, ...)
			 */
			if (((prev_digit % 10000) / 10) == 666 && prev_digit % 10 != 6) {
				for (int i = 0; i < 1000; i++) {
					if (count == n) {
						System.out.print(prev_digit * 1000 + num);
						return;
					}
					num++;
					count++;
				}
				prev_digit++;
			}

			// 선수 자릿수가 X...666 일 경우 (ex. 666_000, 1666_004, ...)
			else if (prev_digit % 1000 == 666) {
				num = 0;
				for (int i = 0; i < 1000; i++) {

					if (count == n) {
						System.out.print(prev_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				prev_digit++;
			}

			// 선수 자릿수가 X...66 일 경우 (ex. 66_600, 166_600, ...)
			else if (prev_digit % 100 == 66) {
				num = 600;
				for (int i = 0; i < 100; i++) {
					if (count == n) {
						System.out.print(prev_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				prev_digit++;

			}

			
			// 선수 자릿수가 X...6 일 경우 (ex. 6_660, 16_663, ...) 
			else if (prev_digit % 10 == 6) {
				num = 660;
				for (int i = 0; i < 10; i++) {
					if (count == n) {
						System.out.print(prev_digit * 1000 + num);
						return;
					}
					num++;
					count++;
				}
				prev_digit++;
			} 
			
			// 그 외의 경우 (ex. 241_666, 23_666 ...)
			else {
				num = 666;
				if (count == n) {
					System.out.print(prev_digit * 1000 + num);
					return;
				}
				count++;
				prev_digit++;

			}
		}
	}
}

 

 

필자가 말한 방법이다.

각 선수 자릿수의 값에 따라서 경우의 수를 나눠 생각하는 방법이다.

즉, 선수 자릿수와 나머지 자리의 수를 조합하여 666이 포함되어 있는 경우만 count 하기 때문에 전체 수를 검사 할 필요가 없어 반복 횟수가 엄청나게 줄어든다는 장점이 있다. 

 

 

종이에 적어주면서 설명하면 어떻게든 쉽게 설명하겠는데,, 글로만 설명하려니 필자도 답답하지만 최대한 이해하기 쉽도록 코드를 정리하여 올렸으니 최대한 이해할 수 있길 바란다.

 

 

---

- 방법 4 

 

 

 

위 알고리즘에서 Scanner 대신 BufferedReader 을 사용한 방법이다.

 

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

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) {
			func(N);
		} 
		else {
			System.out.println(666);
		}
	}

	public static void func(int n) {
		int count = 1;
		int prev_digit = 0;	// 선수 자릿수
		int num = 0;	// 선수 자릿수를 제외한 나머지 뒷 자릿수
		
		/*
		 
		   설명 표현 방법
		   '_'(언더바)를 기준으로 표현한다.  ex) (prev_digit) _ num
		   이 때, 자릿수에 따라서 num 은 0 또는 600, 660, 666 을 갖는다.
		   
		 */
		while (true) {

			/*
			 *  선수 자릿수가 X...666X 이면서 X...6666 이 아닐 경우 
			 *  (ex. 6660_000, 6660_001, ...)
			 */
			if (((prev_digit % 10000) / 10) == 666 && prev_digit % 10 != 6) {
				for (int i = 0; i < 1000; i++) {
					if (count == n) {
						System.out.print(prev_digit * 1000 + num);
						return;
					}
					num++;
					count++;
				}
				prev_digit++;
			}

			// 선수 자릿수가 X...666 일 경우 (ex. 666_000, 1666_004, ...)
			else if (prev_digit % 1000 == 666) {
				num = 0;
				for (int i = 0; i < 1000; i++) {

					if (count == n) {
						System.out.print(prev_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				prev_digit++;
			}

			// 선수 자릿수가 X...66 일 경우 (ex. 66_600, 166_600, ...)
			else if (prev_digit % 100 == 66) {
				num = 600;
				for (int i = 0; i < 100; i++) {
					if (count == n) {
						System.out.print(prev_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				prev_digit++;

			}

			
			// 선수 자릿수가 X...6 일 경우 (ex. 6_660, 16_663, ...) 
			else if (prev_digit % 10 == 6) {
				num = 660;
				for (int i = 0; i < 10; i++) {
					if (count == n) {
						System.out.print(prev_digit * 1000 + num);
						return;
					}
					num++;
					count++;
				}
				prev_digit++;
			} 
			
			// 그 외의 경우 (ex. 241_666, 23_666 ...)
			else {
				num = 666;
				if (count == n) {
					System.out.print(prev_digit * 1000 + num);
					return;
				}
				count++;
				prev_digit++;

			}
		}
	}
}

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

위에서 부터 순서대로

 

채점 번호 : 20051956  -  방법 4 : BufferedReader

채점 번호 : 20051956  -  방법 3 : Scanner

채점 번호 : 20051956  -  방법 2 : BufferedReader

채점 번호 : 20051956  -  방법 1 : Scanner

 

 

보다시피 브루트포스를 사용한 것 보다 666이 들어가있는 경우의 수만 체크하는 경우가 메모리, 시간 모두 압도적으로 빠르다. (물론 코드는 그만큼 길어졌지만..)

그리고 입력 방식에서도 BufferedReader 가 빠른건 이제는 말안해도 척이다.

 

---

• 정리

 

이렇게 브루트포스 카테고리의 마지막 문제가 끝났다.

브루트포스의 경우 맨 첫 포스팅에서도 언급했듯이 모든 경우의 수를 대입해보기 때문에 조건을 만족하는 값을 100% 찾아낸다는 것이 가장 장점이지만 반대로 모든 경우의 수를 대입하다보니 데이터양이 어마어마하다는 것이 단점이다.

 

그렇다보니 경우의 수를 체크할 때, 어떤 경우에서도 불가능한 경우의 수는 최대한 제외를 해주는 것이 가장 좋은 점이긴 하다. (그러나 암호화된 다이제스트의 원문을 얻기 위해서는 그냥 모조리 대입하는 방법 외에는 다른 방법이 있을까나.. (기껏해야 null 일 때..?)

 

어쨌건 단계별 풀어보기 카테고리에서 점점 내용이 어려워지고 있는 사이에 잠깐의 쉬는 시간(?)같은 카테고리라 모두 그리 어렵게 느껴지지는 않았을 것이라 본다.

 

(다음 카테고리는 정렬(매우매우 중요한)이니.. 포스팅 하나 쓰는데 시간이 몇 배로는 더 들 것 같다..)

 

 

 

 

 

 

 

그리고 코드야 베껴가는 건 상관 없는데 (애초에 모두 같이 보고 수정하고 하라고 드래그가 가능하도록 했으니..)혹여 복붙해서 올리시더라도 잘 봤다는 댓글 하나라도 남겨주세요ㅠ 필자가 다른 코드들 볼 때 제 코드가 보일 때마다 가끔은 서럽다는 건 안 비밀입니다.