[PS] BOJ1515 수 이어 쓰기 ( 그리디 ) with JAVA

1515번: 수 이어 쓰기

 

 

◎ 문제풀이

 

1부터 N까지 공백없이 이어붙인 수열에서 임의로 몇 개의 수가 제거되었을 때, 제거된 수열만보고 N의 최솟값을 알아내는 문제이다.  수열의 좌측의 수부터 하나씩 그 수를 포함하는 수의 최솟값을 구하면된다. 

 

 

 

 

 

 

134211 이 임의로 제거된 수열이라고 해보자.

 

가장 좌측인 1을 포함하는 수의 최솟값은 1이다. 

그 다음 3을 포함하는 수의 최솟값은 3이다. 

그 다음 5를 포함하는 수의 최솟값은 5이다. 

그 다음 2를 포함하는 수의 최솟값은 2이다.

그 다음 1을 포함하는 수의 최솟값은 13이다.

그 다음 1을 포함하는 수의 최솟값은 14이다.

 

그러므로 최소 1부터 14까지 이어붙인 수의 나열이라고 할 수 있다.

 

이런 원리로 1 부터 1씩 증가시켜 제거된 수를 포함하고 있는 수를 찾으면 된다. 

수를 찾으면 수가 2자리 이상인 경우, 수열의 수를 포함하고 있을 수 있으므로 모든 자리의 수를 검사한다. 

 

 

◎ 코드

package org.example;

import java.util.*;

//BOJ1515 수 이어 쓰기
public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String input = sc.next();

        char[] arr = input.toCharArray(); // 임의로 수가 제거된 수열
        int arrP = 0; // 수열 포인터

        int ans = 1; 

        while(arrP < arr.length){

            String num = Integer.toString(ans);
            
            // num이 2자리수 이상인 경우, 모든 자리를 검사하기 위해 반복문 돌림
            for(int i=0;i<num.length();i++){
                if(num.charAt(i) == arr[arrP]){ // 수가 포함된 경우
                    arrP++; // 포인터 이동
                }
                if(arrP >= arr.length) break;
            }
            ans = ans + 1;
        }
        System.out.println(ans-1);
    }
}