https://school.programmers.co.kr/learn/courses/30/lessons/42883
가장 큰 수를 만든다 -> 앞자리가 큰 숫자가 오는 것이 큰 수
앞자리에 큰 것만 남기기 위해서는 어떤 자료구조를 사용할 수 있을까?
➡️ 스택
스택의 top과 들어오는 수를 비교해서
+) k개 제거할 수 있으므로
#include <bits/stdc++.h>
using namespace std;
string solution(string number, int k) {
string answer = "";
stack<char> S;
S.push(number[0]);
for (int i=1; i<number.size(); i++){
while (k >0 && !S.empty() && number[i] > S.top()){
S.pop(); k--;
}
S.push(number[i]);
}
if (k-- > 0 && !S.empty()) S.pop();
while (!S.empty()){
char c = S.top(); S.pop();
answer = c + answer;
}
return answer;
}
큰 수 만들기, 앞자리에 큰 수만 남겨놓아야할 때는 스택을 꼭 꼭 생각하자!
+) 그래도 number의 크기(10^6)을 보고 이중 for문과 완전 탐색은 시간복잡도 1초 이내로 불가능하다는 것을 계산한 것은 아주 잘했다!👏
구현, 스택, 그리디 열심히 풀어야겠다. 유형별로 풀어보니까 보완할 유형이 보이기 시작했다. 그리고 무엇보다 가장 중요한 거! 미리 판단하지 말자. 이거 완전 내가 가지고 있는 클루지다!!!
공감하며 읽었습니다. 좋은 글 감사드립니다.