백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 2812 크게 만들기 [ 스택 ]

백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 2812 크게 만들기 [ 스택 ]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

 

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

문제풀이 소감 🧑‍💻

 

스택으로 접근했지만 막 쉽지는 않았던 문제다.

 

 

요구사항 📋

• 주어질 숫자의 개수 N과 삭제할 숫자 개수 K가 주어진다
• 주어진 숫자에서 K개의 숫자를 제거하여 만들 수 있는 가장 큰 수를 구하여라.
• 숫자의 위치는 바꿀 수 없다.
• 삭제한 뒤 남은 숫자들만 그대로 이어 붙어야 한다.

 

주의 ❗

 

2 1
54

 

Answer : 5

 

한 번 순회 이후에 추가적으로 처리를 안해주면 이 반례가 통과하지 못할 것이다.

 

 

해결 전략 📝

 

처음에 잠깐 순열...? 을 생각했는데

 

경우의 수를 생각해보니 생각이 쏙 들어갔다.

 

뭔가 서로 순서가 바뀌지는 않으니 스택을 사용하는 문제라는 직감이 확 들었다.

 

그럼 이걸 어떻게 풀 것인가.

 

 

우선 확실한 건

 

191111 가 나왔다 쳤을 때 앞에 1은 절대 숫자에 포함될 수 없다.

 

왜냐면 무조건 삭제할 숫자는 1개 이상이고 (삭제할 숫자 갯수가 없을 수도 있다면, 얘기가 달라진다.)

 

1 다음 9가 있는데 1을 남겨두는것이 오히려 숫자를 작게 만들어버리는 셈이기 때문이다.

 

여기서 큰 숫자가 나오면 큰 숫자를 우선적으로 남겨야한다는 아이디어를 얻을 수 있다.

 

이 아이디어가 이 문제 해결의 핵심이다.

 

 

ex)

 

39625

 

87235

 

 

라는 예시가 있을 때 K가 2라고 가정해보자.

 

 

직관적으로 첫번째 답은 965, 두번째 답은 875 라고 생각이 들 것이다.

 

당연히 감각적으로 큰 수를 우선적으로 확인하여 최대한 남기려고 하고 작은 수를 최대한 삭제하려고 했을 것이다.

 

이 생각을 코드로 그대로 구현하면 된다.

 

앞에서부터 확인해가면서 앞에 숫자보다 뒤의 숫자가 큰 경우 앞에 숫자를 삭제해준다.

 

스택을 사용한다면 맨 뒤에 있는 숫자를 pop하는 것이다.

 

하지만, 주의 해야할 점은 무조건 삭제가 아닌 K개만 삭제하면 되기때문에 삭제할 갯수가 아직 0이 아닌지를 확인해준 뒤에 삭제해도 된다 했을때 삭제하는 것이다.

 

아무리 1같은 작은 숫자여도 더이상 삭제할 필요가 없다면 당연히 그대로 스택에 쭉 담아주면 된다.

 

 

 

 

한마디로 앞부터 순서대로 작은 숫자들을  최대한 삭제하고, 큰 숫자들을 최대한 남기는 것이다.

 

하지만, 작다고 무조건 삭제하는 것이 아닌 뒤 숫자보다 작은 경우이다.

 

 

또한, K도 고려해야한다.

 

예시가 11911 일때

 

K가 2라면 당연히 앞에 두개를 삭제하면 되지만,

 

K가 1이라면 1911이 답이 되게 된다.

 

 

한 번의 순회를 해서 마쳤을때 그대로 종료하면 안된다.

 

stack에는 값을 무조건적으로 넣어주었기 때문에 마지막 값이 잘못 들어갔을 수도 있다.

 

이 경우 아직 K가 0으로 초기화 되지 않은 상태일 것이다.

 

그러므로 K가 0이 될때까지 stack에서 pop을 실행하여 잘 못 들어온 값을 빼준다.

 

 

ex)

 

2 1
54

 

순회를 마치게 되면 스택에 [5, 4] 가 담겨있다.

 

하지만, K가 아직 1인 상태이므로 4를 pop 시켜 K를 0으로 만들어준다.

 

그러면, 답은 5가 되게 된다.

 

 

 

정답 💯

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [input_N, input_K] = input[0].split(" ").map(Number);

function solution(N, K, nums) {
  const del = (stack, K) => {
    stack.pop();
    return [stack, K - 1];
  };

  let stack = [];
  nums.split("").forEach((num) => {
    while (K > 0 && stack[stack.length - 1] < +num) {
      [stack, K] = del(stack, K);
    }
    stack.push(+num);
  });
  
  while (K !== 0) {
    [stack, K] = del(stack, K);
  }

  return stack.join("");
}

console.log(solution(input_N, input_K, input[1]));