[ 알고리즘 ] 코딩 - Programmers - 큰 수 만들기

* Programmers - Level 2 - 큰 수 만들기

* number 숫자열에서 k개의 수를 제거하고 남은 수 중 가장 큰 수를 찾는 문제 
* number의 자릿수가 무려 100만 자리. 1,000,000 보다 작은 수가 아니다!! 주의하자 
* 자리수인거 인지 못하고 작은 수라고 생각하고 코딩하면 런타임 에러가 발생한다. 
* Deque를 사용했고 숫자를 제거할때는 stack을 이용, 출력할때는 Queue를 썼다. 

입출력예시

---

* 아래와 같은 로직으로 구현했다.

k만큼 제거 성공한 경우

제거가 이루어지지 않고 모든 수가 넘어간 경우

---

import java.util.Deque;
import java.util.LinkedList;
class Solution {
    private static StringBuilder resMax;
    public String solution(String number, int k) {
      int numberLength = number.length();
		StringBuilder answer = new StringBuilder();
		
        // 앞의수와 비교할때는 stack으로 결과 출력할 때는 queue로 이용
		Deque<Character> deque = new LinkedList<>();
		
		deque.offer(number.charAt(0)); // 가장 처음 숫자 데크 적립
		
        // idx : number의 현재 자리
        // discard : 제거한 수의 개수
		int idx = 1, discard = 0; 
		while(true) {
			if(idx == numberLength) { // k개의 숫자를 제거하지 못한 경우
				while(!deque.isEmpty()) { // 일단 제거 완료된 숫자만을 뽑는다
					answer.append(deque.pollLast());
				}
				int remain = numberLength - k; // 남겨야 할 숫자의 개수
                // 큰수가 앞에 있으므로 0번부터 남길 수만큼 substring
				String tmpanswer = answer.substring(0, remain); 
				answer = new StringBuilder();
				answer.append(tmpanswer); // answer로
				break;
			}
			char next = number.charAt(idx);
			char peek = deque.peekFirst(); // 바로 이전에 들어간 수
			if(peek < next) { // 비교했을 때 새로운 수가 큰 경우 이전 값 제거후 적재
				deque.pollFirst(); // 이전 수 제거
				discard++; // 제거 개수 + 1
				if(discard != k){ // 개수 + 1 했을 때 모두 제거했으면 출력으로
					while(true) {
						char pre = '0';
						if(!deque.isEmpty()) {
							pre = deque.peekFirst(); // 가장 마지막의 수를 보자
							if(pre < next) { // 현재 값보다 작은 경우
								deque.pollFirst(); // 제거
								discard++;
								if(discard == k) break;
							} else {
								break;
							}
						} else break;
					}
				}
				deque.push(next); // 현재 적재할 수 보다 큰 수는 다 남기고 그 뒤에 적재
			}
			else { // 현재 들어갈 수가 앞의 수 보다 작으면 그냥 적재
				deque.push(next);
			}
			idx++; // 자리수 이동
			if(discard == k) {
				while(!deque.isEmpty()) { // 제거 하고 남은 가장 큰 수들
					answer.append(deque.pollLast());
				}
                // 그 뒤에 나머지 number를 달아준다
				answer.append(number.substring(idx, numberLength));
				break;
			}
		}
		return answer.toString();
	}
}