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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

문제 분석

[제한 조건]

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

문자열 number 가 주어지고 주어진 문자열 number 로 부터 k 개의 숫자를 제거했을 때 만들 수 있는 가장 큰 순자를 문자열 형태로 리턴하는 문제이다.

 

number = "1924" , k = 2 일 경우 1과 2를 제거해서 만든 "24" 가 리턴되어야 한다.

 

우선 number의 크기가 10^6  이기 때문에 O(n^2) 로는 풀지 못한다. (완전탐색은 불가능)

문제 접근

만들 수 있는 경우를 다 만들고 그 중 가장 큰 숫자를 선택하는 방법 (완전탐색) 으로는 해당 문제를 해결하지 못한다.

주어지는 문자열의 크기가 완전탐색을 적용시키기 너무 크다.

 

그렇다면 for 문 한번으로 스캔하면서 문제를 풀어야 하는데 이럴 경우에는 생각할 수 있는 방법으로는

Map 자료구조를 활용하여 앞에 나왔던 것들을 기록해두는 방법이 있을 수 있고,

Stack 자료구조의 특징을 활용할 수 있다면 이를 이용해 문제를 해결하는 방법이 있을 수 있다.

 

해당 문제는 앞에 작은 숫자가 먼저오면 전체 숫자가 작아진다는 특징이 있다.

Stack 자료구조의 특징을 잘 활용한다면 해당 문제를 해결할 수 있을 것 같다.

 

스택에 숫자를 하나씩 push 해주는데,

앞에 나보다 작은 숫자들이 있다면 전부 pop 해주고 자신을 넣는다.

 

pop 은 k 의 개수 만큼만 할 수 있도록 제한하고, 마지막에 k가 남을 수 있기 때문에 남은 k 만큼 pop을 더 해준다.

스택에 숫자를 하나씩 push 해주는데,
앞에 나보다 작은 숫자들이 있다면 전부 pop 해주고 자신을 넣는다.


pop 은 k 의 개수 만큼만 할 수 있도록 제한하고, 마지막에 k가 남을 수 있기 때문에 남은 k 만큼 pop을 더 해준다.

 

코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        Stack<Character> stack = new Stack<>();
        
        for(char c : number.toCharArray()){
            if(stack.isEmpty()){
                stack.push(c);
            }else{
                while(!stack.isEmpty() && stack.peek() < c && k > 0){
                    stack.pop();
                    k--;
                }
                stack.push(c);
            }
        }
        
        for(int i=0; i<k; i++){
            stack.pop();
        }
        
        for(char c : stack){
            answer += c;
        }
        return answer;
    }
}