백준 1515번 : 수 이어 쓰기 (자바)

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

---

문제

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

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

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

남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)

---

입력

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

---

출력

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

🔵풀이

생각보다 고전했던 문제입니다. 여러 방법을 고민하다 그냥 완전탐색으로 풀어버렸습니다. 수를 1부터 증가시키며 만약 포함하고 있다면 그다음 배열의 수로 넘어갔습니다.

 

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

public class Main {
  public static  void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
    char[] arr = str.toCharArray(); //한 숫자씩 나누기
    int pointer = 1; //1부터 증가할 숫자

    for (int i=0; i<arr.length; i++){
      while (true) {
        if (String.valueOf(pointer).contains(String.valueOf(arr[i]))) { //만약 배열의 수를 포함한다면
          int idx = String.valueOf(pointer).indexOf(String.valueOf(arr[i])); 
          String tmp = String.valueOf(pointer).substring(idx+1); //포함된 수 앞쪽을 제외하고 뒤쪽 수
          int count = 1;
          while (i+count<arr.length&&tmp.contains(String.valueOf(arr[i+count]))) {//뒤 배열의 수도 포함할 수 있는지 검사 반복
            idx = tmp.indexOf(String.valueOf(arr[i+count]));
            tmp = tmp.substring(idx+1);
            count++;
          }
          i+=count-1;
          pointer++;
          break;
        }
        pointer++;
      }
    }
    System.out.println(pointer-1);

  }
}