백준 1515 - 수 이어 쓰기 (자바 - 그리디)

https://www.acmicpc.net/problem/1515

1515번: 수 이어 쓰기

 

* 문제 요약

세준이는 1 부터 N 까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그러고 나서, 세준이가 저녁을 먹으러 간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.

세준이는 저녁을 먹으러 갔다와서, 자기가 쓴 수의 일부가 지워져 있는 모습을 보고 충격받았다.

세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만 N 이 기억나지 않는다.

남은 수를 이어붙인 수가 주어질 때, N 의 최솟값을 구하는 프로그램을 작성하시오.

(아무것도 지우지 않았을 수도 있다.)

 

* 입력

첫째 줄에 지우고 남은 수를 한 줄로 이어붙인 수가 주어진다. 이 수는 최대 3,000 자리이다.

 

* 출력

가능한 N 중에 최솟값을 출력한다.

 

* 예시

 

* 해결 과정

입력으로 주어지는 수는 최대 3000 자리이고, 0 ~ 9 까지는 10개이다.
그러므로 최악의 경우 3000 * 10 = 30000 번의 연산 이내에 모두 찾을 수 있다.
입력받은 문자열 상의 현재 포인터 위치와 base 숫자의 각 자릿수를 비교해주면서 둘의 값이 같다면 포인터값을 늘려서 다음 값을 비교한다.
포인터와 입력 문자열의 길이가 일치하는 경우. 즉, 문자열을 모두 다 확인 했을 때 현재 base 값을 출력해준다.

 

* 코드

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

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

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String input = br.readLine();

        int pointer = 0;
        int base = 0;

        while (base++ <= 30000) {
            String temp = String.valueOf(base);

            for (int i = 0; i < temp.length(); i++) {
                if (temp.charAt(i) == input.charAt(pointer)) {
                    pointer++;
                }

                if (pointer == input.length()) { 
                    bw.write(base + "\n");
                    bw.flush();
                    bw.close();
                    br.close();
                    return;
                }
            }
        }
    }
}

 

 

매 반복마다 1 씩 늘어나는 숫자를 문자열로 취급하며 입력받은 문자열을 내부에서 포인터로 가리키고 있는 값을 포함하고 있는지 비교하는 방식을 통해 단순히 int 나 long 으로 취급하기는 어려운 숫자를 간편하게 조작하였고

이중 반복문을 통해 현재 base 숫자의 모든 자릿수를 확인 한 다음엔 숫자를 1 늘려 또다시 각 자릿수 별로 확인하는 식으로 1 부터 30000 까지 숫자들 중에서 순서대로 가능한 모든 경우를 대입하여 검사하였으므로 가능한 모든 경우의 수를 찾아보는 브루트포스 알고리즘 문제라고 할 수 있다.