[풀이]
https://school.programmers.co.kr/learn/courses/30/lessons/42883
[문제]
입력 값이 크기 때문에 단순한 이중 반복문으로는 풀 수 없다. 풀이 방식은 오큰수 개념을 활용했다.여기서의 동작은 뒤의 숫자가 클 때 앞의 숫자를 제거하는 방식으로 구현되어있다.
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
// 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 수
// ex) 1924에서 두 개 제거하면 19, 12, 14, 92, 94, 24가 만들어지는데, 이 중 가장 큰 수는 94
// number : 2자리 이상, 1'000'000 이하
// k : 1 이상 number 자릿수 미만 자연수
string solution(string number, int k)
{
string answer = "";
stack<char> Stk;
// 오큰수 전략(앞큰수로 k개 제거하기)
for (char digit : number)
{
// 뒤의 숫자가 클 때 앞의 숫자를 제거
while (!Stk.empty() && k > 0 && Stk.top() < digit)
{
Stk.pop();
k--;
}
Stk.push(digit);
}
// 아직 k가 남아있다면 뒤에서 제거
while (k-- > 0)
{
Stk.pop();
}
// 스택 → 문자열로 변환
while (!Stk.empty())
{
answer += Stk.top();
Stk.pop();
}
reverse(answer.begin(), answer.end());
return answer;
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 Lv.2] 연속된 부분 수열의 합 (0) | 2025.05.20 |
---|---|
[프로그래머스 Lv.2] 삼각 달팽이 (0) | 2025.05.20 |
[프로그래머스 Lv.2] 쿼드압축 후 개수 세기 (0) | 2025.05.19 |
[프로그래머스 Lv.2] 다리를 지나는 트럭 (0) | 2025.05.19 |
[프로그래머스 Lv.2] 두 큐 합 같게 만들기 (0) | 2025.05.19 |