[백준] 1515번 : 수 이어 쓰기 - JAVA [자바]

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

 

---

문제

 

약간의 그리디 알고리즘을 가미한 구현문제이다.

 

입력으로 주어지는 수는 3000자리이고 0~9까지는 10개이다. 3000 * 10 = 30000 이내에서 2초동안 모두 찾을 수 있다.

 

입력값 290119으로 예시를 들겠다.

 

이 문자열의 문자마다 위치를 가르키는 index가 있다.

 

그리고 1 부터 시작하는 값 Num의 각자리수와 비교를 해준다.

 

Num이 2일때를 생각해보자.

 

이때의 index는 0이다. 

 

290119의 0의 인덱스 위치는 2이다. Num과 인덱스 위치의 값이 같기 때문에 index를 증가시킨다. (index = 1)

 

이후 Num이 9일때도 마찬가지로 index를 증가시킨다. (index = 2)

 

그다음 Num이 10일때는 10의 자리수의 값과 index위치의 0의 값은 일치하지 않지만 Num의 1의 자리수의 값과 같기때문에 index를 증가시킨다 (index = 3)

 

이런식으로 완전 탐색을 진행하다 보면 index의 값이 입력값의 길이보다 커질것이다. 이때 이 루프 로직을 종료시킨다면. 그때의 Num 값이 문제가 요구하는 답이 된다.

 

이 문제는 아이디어를 코딩하는 것은 어렵지 않다. 하지만 이 아이디어를 생각하는게 어렵다고 생각된다.

 

---

전체 코드

public class Main {
	
    public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("./input.txt"));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = null;
        
        // 234092
        
        String str = in.readLine();
        int num = 0;
        int index = 0;
        boolean flag = true;
        
        while(flag) {
        	num++;
        	
        	String numStr = Integer.toString(num);
        	
        	for(int i = 0; i < numStr.length(); i++) {
        		char c = numStr.charAt(i);
        		
        		if(c == str.charAt(index)) {
        			index++;
        		}
        		
        		if(index == str.length()) {
        			flag = false;
        			break;
        		}
        	}
        }
        
        System.out.println(num);
        
    }
}

---

결과