[ 프로그래머스 ] 큰 수 만들기 ( 자바)

[ 프로그래머스 ] 큰 수 만들기 ( java)

 

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

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

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

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.

• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스

 

 

 

핵심 

1. numbers 범위만 작았다면, 완탐 또는 dp로 풀 수 있었던 문제다. 처음에 그렇게 접근하려고도 했었지만, numbers범위가 너무 크기 때문에 시간 초과 난다.

 

 

2. 완탐말고 처음부터 새로운 접근법이 필요했다. 

처음으로 돌아가면, numbers의 자릿수는 이미 순서가 정해져 있다. 또한, 만들어야 하는 numbers-k의 구성은 numbers에서 가장 큰 숫자를 찾고, 그 뒤에서 가장 큰 수를 찾고.. 이렇게 쭉 이어서 만들면 되겠다고 생각했다. 

 

가장 큰 수란? numbers에서 가장 큰 수(big)가 num-k자리 숫자의 제일 앞에 오고, 그다음 큰 수가 num-k에 다음에 붙고... 쭉 이어진다고 생각함. 하지만, big을 numbers-k자릿수 제일 앞에 쓰려면, numbers의 제일 앞 자릿수부터 big 전까지 모두 삭제해야 한다. 이 때, 삭제해야하는 문자가 k개 이내라면 문제가 없다. 하지만, big까지 도달하는데 k개를 넘는다면?

=> 이미 숫자 간에 순서가 정해져 있기 때문에 가정대로 만들기 불가능.

그렇다고 dp로 풀릴 문제가 아닌데 dp로 풀려고 했다.

 

 

3. 탐색하며 매 순간 최선의 선택

순서 때문에 numbers를 앞에서 탐색한다. 그리고 탐색하며 만나는 숫자가 'num-k'가 가장 큰 수가 될 수 있도록 해야 한다. 결국, 문제가 요구하는 내용이랑 같네

그럼, 탐색하는 과정에서 최대 'num-k'를 구할 수 있을까? 불가능. 앞으로 어떤 자리를 k만큼 빼야 할지 모르기 때문. 그래서, 탐색하는 동안 'num-k'의 최대를 유지하는 것이 아닌 내림차순 정렬? 을 유지해야 한다. 탐색 과정에서는 최대가 아니지만, 탐색이 끝나면 최대가 되기 위해서.

 

 

how?  

'num-k' 자리가 내림차순으로 유지되어야 한다. ( 큰 수가 제일 앞에 위치 ) 그래서 탐색하면서 만나는 숫자는 'num-k'에 들어가 내림 차순 정렬되는데, 'num-k'뒤에서부터 검사한다. 

새 숫자보다 작은 숫자가 나오지 않을 때까지 삭제. (k 이내) 그리고 뒤에 붙인다. 

(k개 삭제 => k개를 무조건 빼야한다. k개를 빼지 않게 루프가 끝나는 케이스 고려하기)

 

 

ex

4 1 7 7 2 5 2 8 4 1, k = 4

0 1 2 3 4 5 6 7 8 9  

 

index 0일 때, 최대되려는 숫자 4

index 1일 때, 최대되려는 숫자 41

index 2일 때, 최대 되려는 숫자 7  -> 4, 1이 7보다 작으므로 2 숫자를 제거했다. 그리고 7을 뒤에 붙인다. 

이렇게 4, 1 같은 경우 막 제거해도 괜찮을까? ㅇㅇ k개 전까지는 삭제해도 됨. 

 

index 3일 때, 최대되려는 숫자  77

index 4일 때, 최대되려는 숫자  772

index 5일 때, 최대 되려는 숫자 775 -> 2가 5보다 작아서 제거하고, 7은 더 크기 때문에 제거 못하고 뒤에 5를 붙인다. 

index 6일 때, 최대 되려는 숫자 7752

index 7일 때, 최대 되려는 숫자 7758 -> 2가 8보다 작아서 제거했다. 그런데 최대 4번만 제거가 가능해서 더 이상 제거 못하고 그대로 이어 붙인다. 

 

index 8 이후는 더 이상 삭제가 불가능하여 그대로 붙이면, 775841

 

 

temp는 stack. 

for ( cur : 모든 numbers에 대해 )

    while ( temp의 제일 뒷자리 값 < cur 값 && k > 0 ) 

        temp이 제일 뒷자리 제거 

        k-- 

    temp에 cur 값 저장

 

( 내림차순 정렬을 만들 때, k개를 삭제하지 못한 경우 따로 처리해줘야 한다. )

temp가 답

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

 

코드

import java.util.Stack;
class Solution {
	public String solution(String number, int k) {
		char[] input = number.toCharArray();
		
		// 스택, 작은 수 일수록 위에 존재한다. 
		Stack<Character> temp = new Stack<>(); 
		for(int i = 0 ; i < input.length ; i++) {
			while(!temp.empty() && k > 0 && temp.peek() < input[i]) {
				k--;
				temp.pop();
			}
			temp.push(input[i]);
		}
		StringBuilder sb = new StringBuilder();
		// k개를 삭제하지 못 한 경우 뒤에서 부터 제거. 
		while(!temp.empty()) {
			if(k != 0) {
				temp.pop();
				k--;
			}else {
				sb.append(temp.pop());
			}
		}
		return sb.reverse().toString();
	}
}