[백준 온라인저지]영화감독숌 - 브루트포스(5)

영화감독 숌

이번 포스팅 문제는 1436번 문제입니다. 이 문제는 정답률이 50%가 안되네요.. 이문제 역시 브루트포스 알고리즘을 사용하여 풀이했습니다.

문제요약

666을 포함하는 숫자중에 작은수부터 n번째 숫자를 찾는 문제입니다. 예를 들어 1번째 666을 포함하는 숫자는 666이고 2번째 666을 포함하는 숫자는 1666 입니다. 

풀이전략

1. 1부터 무한대까지 숫자를 검사

2. 각 숫자가 666을 포함하는지 검사

3. 666을 포함하면 count를 1씩 증가시키고 입력받은 n과 같으면 출력

구현하기

package BackJoon.브루트포스;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/1436
 * @author troh
 *
 */
public class _1436_영화감독숌 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int count = 0;
        int num = 0;
        while(n != count) {
            num++;
            if(isEndNumber(num)) {
                count ++;
            }
        }
        System.out.println(num);
    }
    
    private static boolean isEndNumber(int num) {
        int temp = num;
        while(temp > 100) {
            if(temp%10 == 6 && temp/10 % 10  == 6 && temp/10/10 % 10 == 6) {
                return true;    
            }
            temp = temp/10;
        }
        return false;
    }
}
 

배운점

처음에는 n번째 숫자를 만드려고 했는데 패턴이 너무 어려운 것 같아 1부터 숫자를 증가시키며 666을 포함하는지 체크하는 식으로 관점을 바꿨습니다. 666을 체크하는 알고리즘은 처음에는 String을 이용하여 "666"을 포함하는지 검사하였는데 메모리와 수행속도가 너무 높아서 알고리즘을 변경하였습니다.