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

문제 링크 : https://www.acmicpc.net/problem/1436

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

 

방법 1 |

import java.io.*;
import java.util.*;

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 series_number = 666;
			
			while(N > 0) {
				if(Integer.toString(series_number).contains("666")) {
					N--;
				}
				series_number++;
			}
			System.out.println(series_number-1);
	}
}

 문제를 푸는 가장 간단한 방법이다. 이 문제는 브루트 포스 카테고리에 포함되어 있는 문제인데 그것에 걸맞게 입력한 숫자까지 모두 검사하여 "666"이 들어있으면 입력한 값을 0까지 감소시켜 결과 값을 구하는 알고리즘이다. 문자열에 특정 문자열이 포함되어 있는지 확인하는 contains 메소드를 활용한다.

 

 채점 결과는 맞았다고 나왔지만 진짜 입력한 N까지의 수를 모조리 검사하는 방식이라 상당히 무식하다는 생각이 들었다. 그래서 규칙성을 찾기 위해 직접 N번째의 영화 제목에 들어갈 수를 적어보기도 하고, 인터넷에 다른 분들이 풀어놓은 알고리즘을 찾아보기도 하였다.

 

방법 2 |

 contains 메소드를 활용하지 않고 한정된 범위의 숫자만을 확인하는 방법은 없을까? 666, 1666, 2666, .... 숫자를 자세히 들여다보니 마지막 666은 변하지 않고 천의 자리 숫자만 증가하는 것을 확인할 수 있었다. 천의 자리 숫자가 6이 될 경우에만 6660, 6661, 6662, ... 이런 방식으로 10개의 숫자가 더 나열되었다. 문제에서 주어지는 입력값은 최대 10000이고, 앞선 방법1에서 10000을 넣어보니 값이 2666799가 나왔다. 그렇다면 7번째 자리까지 천의 자리 숫자를 검사하면 쉽게 구할 수 있지 않을까?

import java.io.*;
import java.util.*;

public class Main {
	public static void findCount(int N) {
		int count = 1;
		int num = 0;
		int leading_digit = 0;
		
		while(true) {
			if(((leading_digit) % 10000) / 10 == 666 && leading_digit % 10 != 6) {
				for(int i = 0; i < 1000; i++) {
					if(count == N) {
						System.out.println(leading_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				leading_digit++;
			}
			
			else if(leading_digit % 1000 == 666) {
				num = 0;
				for(int i = 0; i < 1000; i++) {
					if(count == N) {
						System.out.println(leading_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				leading_digit++;
			}
			
			else if (leading_digit % 100 == 66) {
				num = 600;
				for(int i = 0; i < 100; i++) {
					if(count == N) {
						System.out.println(leading_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				leading_digit++;
			}
			
			else if(leading_digit % 10 == 6) {
				num = 660;
				for(int i = 0; i < 10; i++) {
					if(count == N) {
						System.out.println(leading_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				leading_digit++;
			}
			
			else {
				num = 666;
				if(count == N) {
					System.out.println(leading_digit * 1000 + num);
					return;
				}
				count++;
				leading_digit++;
			}
		}
	}
    
	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) {
				findCount(N);
			}
			else {
				System.out.println("666");
			}
	}
}

 전체 코드이다. 코드가 길어서 설명만 나열하면 이해하기 힘들 수 있으므로 하나씩 분리해서 설명하겠다.

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

 우선 Main 함수이다. N에 몇 번째 영화 제목에 들어가는 숫자를 구할 것인지 입력 받고 만약 1이면 무조건 "666"이므로 그대로 출력한다. 만약 아니면 findCount() 함수를 사용해 N번째 영화 제목에 들어가는 숫자를 구한다.

	public static void findCount(int N) {
		int count = 1;
		int num = 0;
		int leading_digit = 0;

 findCount 함수의 처음 부분이다. count 함수의 경우 계산하는 숫자가 몇 번째 영화 제목에 들어가는 숫자인지 계산하는 변수이다. num은 백의 자리까지 숫자를 담는 변수이다.

 

 num은 아까 말했듯이 666, 1666, 2666, ... 이런 식으로 증가하다가 5666 다음의 6660 처럼 천의 자리부터의 숫자가 특정 숫자가 되면 더이상 증가하지 않고, 백의 자리 숫자만 증가한다. 6_660, 6_661, 6_662, ... 이런 식이다. 그리고 자리 수가 늘어날수록 이렇게 필터링 해야하는 경우의 수가 늘어난다. 가령 자리 수가 5개인 숫자이면 66600, 66601, 66602, ... 이렇게 백의 자리까지 숫자가 600부터 699까지 100개나 있다. 만약 자리 수가 6개이면 666000, 666001, 666002, ... 백의 자리까지 숫자가 000부터 999까지 1000개이다. findCount() 함수에서는 if-else 문으로 이런 경우들을 모두 걸러줄 것이다.

 

 num 변수에서 설명했듯이 천의 자리 이상 숫자를 가리키기 위해 사용되는 변수가 leading_digit이다. num의 경우는 각 if-else문에서 경우에 맞는 num 값으로 초기화시키지만 leading_digit은 처음부터 끝까지 반복문이 끝날 때까지 증가하기만 한다.

			else {
				num = 666;
				if(count == N) {
					System.out.println(leading_digit * 1000 + num);
					return;
				}
				count++;
				leading_digit++;
			}

 다음은 while(true) 반복문으로 N번째 영화 제목에 들어가는 숫자가 발견되면 탈출하는 조건을 가진 무한루프이다. if문보다 마지막 else문부터 역행으로 봐야 이해가 쉬울 것 같아서 마지막 else문부터 가져왔다. 이 else문은 백의 자리까지 숫자가 666일 경우를 센다. 처음에 666, 1666, 2666, ... 이렇게 늘어나는 숫자열을 연상시키면 이해하기 쉽다.

 

 그리고 count가 증가하면서 입력으로 주어진 N값과 일치하면 N번째 영화 제목에 들어가는 숫자를 출력하고 return으로 반복문을 탈출한다. break가 아닌 return으로 탈출한 이유는 원하는 결과값을 찾았으므로 findCount() 함수를 종료시키고 Main() 함수로 돌아가기 위해서이다.

			else if(leading_digit % 10 == 6) {
				num = 660;
				for(int i = 0; i < 10; i++) {
					if(count == N) {
						System.out.println(leading_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				leading_digit++;
			}

 else문 바로 위에 적히는 else-if 문이다. 조건이 leading_digit을 10으로 나누었을 때 나머지가 6일 경우로 제시했다. 이게 무슨 말이냐면 6_660을 생각하면 이해하기 쉽다. 6660, 6661, 6662, ... 이렇게 증가할 때 count를 증가시키는 것이다. 일의 자리 숫자가 0부터 9까지 10번 반복할 때까지만 세기 때문에 for문도 10번만 반복하도록 하였다. 그 사이에 해당하는 결과 값을 찾으면 출력하고 findCount() 함수를 종료시킨다.

			else if (leading_digit % 100 == 66) {
				num = 600;
				for(int i = 0; i < 100; i++) {
					if(count == N) {
						System.out.println(leading_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				leading_digit++;
			}

 이제부터는 이해하기 쉬우리라 생각한다. 66_600일 경우이다. 66600, 66601, 66602, ... 이렇게 100번 반복한다.

			else if(leading_digit % 1000 == 666) {
				num = 0;
				for(int i = 0; i < 1000; i++) {
					if(count == N) {
						System.out.println(leading_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				leading_digit++;
			}

 666_000일 경우이다. 666000, 666001, 666002, 666003, ... 이렇게 1000번 반복한다.

		while(true) {
			if((leading_digit % 10000) / 10 == 666 && leading_digit % 10 != 6) {
				for(int i = 0; i < 1000; i++) {
					if(count == N) {
						System.out.println(leading_digit * 1000 + num);
						return;
					}
					count++;
					num++;
				}
				leading_digit++;
			}

 가장 최상단에 있는 if문이다. 이 조건은 아래 else-if문에서 count에 추가했을 경우, 즉 중복되는 경우들을 걸러내기 위한 조건이다. 6660000, 6660001, 6660002, ... 이런 경우를 세는데 6660_XXX가 아니고 6666_XXX가 되어서 천의 자리 숫자가 6이 되어버리면 바로 아래 else-if문, leading_digit % 1000 == 666인 경우와 겹치는 숫자가 발생한다. 그래서 천의 자리 숫자가 6인 경우를 제외시키고 count를 증가시킨다.

 

 count와 N 값이 일치하면 원하는 N번째 영화 제목에 들어갈 숫자를 찾았다는 의미이므로 findCount() 함수 내에서 결과값을 출력하고 함수를 종료시킨다.

 

 방법1(300ms)에 비해 출력시간이 절반 이하로 줄어든 것을 확인할 수 있다.

 

 

 

※ 방법2 참고한 블로그 주소 : https://st-lab.tistory.com/103