큰 수 만들기

유태형·2022년 2월 16일

코딩테스트 프로그래머스

프로그래머스 - Level 2

목록 보기

20/36

문제

문제 분석

1.k개의 숫자를 제거했을때 최대값이 되어야 한다.
2.숫자들간 순서는 유지되어야 한다.

풀이

스택 사용

최대값을 유지해야고 이전 값과 비교해야 하므로 스택을 사용
현재 값과 이전 최대값을 비교해 이전 스택의 값들이 더 크면 push, 현재 값이 더 크면 스택의 값이 더 클때까지 pop을 수행한다.

stack.peek() < c

top의 값이 새로 들어온 값보다 작으면 제거

k-- > 0

자리수를 맞춤

코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        //결과를 담을 배열
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();
        
        //문자열에서 한 숫자씩 (순서는 지켜야 함)
        for(int i = 0; i < number.length() ; i++){
            char c = number.charAt(i); //현재 숫자
            //스택이 비지 않고, 현재 값이 더 크고 제거해야 할 숫자가 남았을 동안
            while(!stack.isEmpty() && stack.peek() < c && k-- > 0){
                stack.pop(); //숫자 제거
            }
            stack.push(c); //현재 값 스택에 저장
        }
        //스택의 값 처음부터 (순서는 지켜야 함)
        for(int i = 0; i < stack.size(); i++){
            result[i] = stack.get(i);
        }
        return new String(result);
    }
}