[Lv2] 큰 수 만들기

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number	k	return
1924	2	94
1231234	3	3234
4177252841	4	775841

문제 원출처: http://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf

 

---

제외하고 남은 숫자들로 이루어진 return의 숫자들은 원래의 number의 순서를 유지해야합니다.

 

number의 길이가 너무 길어서 처음부터 number를 long으로 바꾸어 하나씩 제거하는 방법은 안됩니다.(가능하더라도 시간 및 메모리 초과)

 

import java.util.Stack;

class Solution {
	public String solution(String number, int k) {
		int anslength = number.length()-k;
		char[] arr = number.toCharArray();		
		Stack<Character> stack = new Stack<>();
		for(int i=0;i<arr.length;i++) {
			while(k>0) {
				if(stack.isEmpty()) break;
				else {
					char prev = stack.peek();
					if(prev<arr[i]) {
						stack.pop();
						k--;
					} else break;
				}
			}
			stack.push(arr[i]);
			if(k==0 && stack.size()==anslength) break;
		}
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<anslength;i++) {
			sb.append(stack.get(i));
		}
		return sb.toString();
	}
}

어차피 앞자리 부터 숫자를 결정해야 큰 수를 만들겠죠.

 

stack에 첫 자리 부터 넣습니다.

 

제외할 횟수 k가 남았다면, stack을 보는데,

 

stack이 비었다면 그냥 넘어가지만,

 

stack의 최근값이 지금값보다 작으면, k를 소모하고 그 작은 값을 날려버립니다.

 

k가 건재한 동안에는 이 짓을 해줘야 앞에서부터 큰 수가 나오고, k를 다 쓰면 그냥 차곡차곡 넣습니다.

 

이제 처음에 구해둔 원래 길이 - k만큼만 stack에서 순서대로 꺼내서 반환합니다.

 

numbers가 55555555처럼 같은 수만 반복되면 k는 소모되지 않은채 number의 모든 값이 stack에 들어가고,

 

이걸 다 반환하면 제외시킨 후의 길이가 아니라 원래 길이가 나오므로, 꼭 numbers 길이 - k 만큼만 반환합니다.

 

(아니면 코드에서 for문에 stack의 size가 원하는 길이가 됐을 때 빠져나오게 하든가)