[프로그래머스] 큰 수 만들기 JAVA 문제 풀이 ( 그리디 ) - 그림설명O

문제 설명

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

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

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

제한 조건

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

입출력 예

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

 

문제 풀이

하나의 스택에다가 문자열을 순서대로 비교하며 큰 수를 넣어주고, 출력시에 이를 리버스해서 빼내면 정답을 도출 할 수 있다.

1️⃣ 일단 비교를 위해 처음 수는 스택에 넣어준다.

2️⃣ 스택.peek() -> 1 과 그 다음 수인 2와 비교하니 2가 더 크다. 1을 제거 ( 스택.pop()으로 빼내고 k를 감소시켜준다.)하고, 2를 스택에 push 해준다

3️⃣ 이런 과정을 거쳐 결국 스택에 3밖에 없는데 3 다음 수인 1과 비교하니 1이 작다. 이땐 그냥 스택에 넣어두자.

4️⃣ 스택.peek() -> 1과 그 다음 수인 2를 비교하니, 2가 더 크다. 아까한대로 제거 과정 후에 2를 스택에 push한다. k가 0이 되었다.

 

해당 과정을 적절한 반복문과 조건문으로 구현했더니 문제가 발생했다.

 

문제 발생

연속된 숫자 일때는 k가 감소되지도 않는다. 즉, 제거 과정이 발동이 안된다.

=> 그냥 예외처리로서 리버스 출력 후에 k 만큼 잘라주었다.

 

 

정답

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        Stack<Character> stStack = new Stack<>();
        
        for (int i = 0; i < number.length(); i++){
            // k가 0이 될때까지 반복, stStack.peek()보다 크면 기존거 제거하고 다시 담기
            while (!stStack.isEmpty() && k > 0 && number.charAt(i) > stStack.peek()){
                    stStack.pop();
                    k--;
            }
            // 스택에 넣기
            stStack.push(number.charAt(i));
        }
        
        // Stack에서 문자를 꺼내서 StringBuilder에 추가
        StringBuilder sb = new StringBuilder();
        while (!stStack.isEmpty()) {
            // 인덱스 0부터 차례대로 -> 리버스
            sb.insert(0, stStack.pop());
        }
        
        // 남은 숫자(5,4,3,2,1일 경우 k가 남음)는 뒤에서 제거
        sb.delete(sb.length() - k, sb.length());
        
        // `StringBuilder`를 문자열로 변환하고 반환
        return sb.toString();
    }
}

 

 

 

큰 수 만들기 큰 수 만들기 큰 수 만들기 큰 수 만들기 큰 수 만들기 큰 수 만들기 큰 수 만들기 큰 수 만들기