백준 1515 자바 - 수 이어 쓰기 (BOJ 1515 JAVA)

문제 : boj 1515

 

 

  입력으로 주어지는 수는 최대 3000자리이고, 0~9까지는 10개이다. 그러므로 대충 생각해봐도 아무리 최악의 케이스라 할지라도 3000 * 10 = 30000 이내에서 모두 찾아질 것임을 알 수 있다.

 

  그러므로 brute force로 입력받은 값을 첫 자리부터 확인하며 1부터 30000까지 입력으로 받은 값에 대입해보며 하나씩 찾아나가면 된다.

 

 

  예를들어 290119을 보자. 첫 자리수부터 확인한다. 여기서 base라는걸 1로 두고, base를 1씩 증가시키며 쭉 매칭시키자. 우선 'base=1'은 현재 pointer가 보고있는 2와 겹치는게 없으니 다음으로 넘어간다. 'base=2'는 pointer와 동일하므로 찾은거다. pointer를 전진한다. 그리고 base가 현재 1자리 수 이므로 더 볼게없으므로 1을 증가시킨다.

  base는 현재 3이다. 매칭되는게 쭉 없다. base=4, base=5, ..., base=9 일 때 현재 pointer와 매칭된다. 마찬가지로 pointer를 증가하고 base도 증가시킨다.

  현재 base=10, pointer는 '0'을 보고 있다. 10을 한 자리수씩 나눠보면 [1, 0]이다. 차례대로 큰 자리수부터 보면 1은 매칭 안되지만 0은 매칭되므로 pointer를 증가시킨다. base도 1의 자리수까지 봤으므로 증가시킨다.

  현재 base=11, pointer는 '1'을 보고 있다. 11->[1, 1] 이다. 차례대로 보자. '1'이 매칭되므로 pointer를 증가시키고, base도 다음자리수를 보면 또 1이고 pointer와 매칭되므로 다시 pointer를 증가시킬 수 있다. base도 다 봤으니 증가시킨다.

  

  현재 base=12, pointer는 '9'를 보고 있다. 쭉 매칭되는게 없으므로 base를 계속 증가시키다가, base=19에서 매칭된다. 다 확인했으므로 현재 base가 '가능한 N 중에 최솟값'이다. 따라서 290119에 대한 답은 '19'가 된다.

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int pt = 0;

        int base = 0;
        while (base++ <= 30000) {
            String tmp = String.valueOf(base);
            for (int i = 0; i < tmp.length(); i++) {
                if (tmp.charAt(i) == s.charAt(pt))
                    pt++;
                if (pt == s.length()) {
                    System.out.println(base);
                    return;
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}