큰_수_만들기.md

큰 수 만들기

문제 링크

문제 설명

주어진 0~ 1,000,000자리 수 범위의 숫자에서 K 갯수의 숫자를 지웠을 때 가장 큰 수를 반환해라

입출력 예시

Input:
	number = "1924"
	k = 2
Output: "94"

문제 풀이

stack을 이용하면 어렵지 않게 풀리는 문제 였다. 앞에 최대한 큰 숫자를 남겨야한다.

1. 앞보다 뒤에 큰 숫자가 있을 때 앞선 값들을 지워준다.
2. 지우는 순서는 앞선 작은 값 부터이다. 위 규칙을 지키는 코드를 짜면 된다.

풀이코드

import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        char[] chs = number.toCharArray();
        int count = 0;
        Stack<Character> stack = new Stack<>(); //int형 스택 선언
        for(char ch :  chs){
          if(stack.size() == 0){
            stack.push(ch);
          }else {
            while( stack.peek() < ch && count < k){
                stack.pop();
                count++;
                if(stack.size()==0) break;
            }
            stack.push(ch);
          }
        }
        String str = "";
        int idx  = 0;
        for(char item : stack){
            str += item;
            idx ++;
            if(idx == number.length() - k){
                break;
            }
        }
        return str;
    }
}

풀이 코드 JavaScript

function solution(number, k) {
  const splittedNember = number.split("");
  let stack = [];
  let count = 0;
  for (let item of splittedNember) {
    if (stack.length == 0) {
      stack.push(item);
      continue;
    }
    while (stack[stack.length - 1] < item && count < k) {
      stack.pop();
      count++;
    }
    stack.push(item);
  }
  if (number.length - k < stack.length) {
    stack = stack.slice(0, number.length - k);
  }
  return stack.join("");
}