[틀림] 프로그래머스 큰수만들기 // 스택, 그리디

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

* 시도1

• min heap에 제거대상을 k 개선택
• vis에 기록
• 앞에서부터 제거대상인지 보고, 제거
• 예제3이 반례였음

 

* 풀이

• 스택이용
  • top < num 인동안
  • 계속 pop 해주기, k--
• 완료후, stack에 남은숫자가 정답
• 엣지케이스, k가 남은경우는 stack에서 k개를 제거해줘야함.

#include <bits/stdc++.h>

using namespace std;
priority_queue<int, vector<int> ,greater<int>> pq;
vector<int> v;
int vis[10]; //제거대상
stack<int> s;

string solution(string number, int k) {
    string answer = "";
    
    for(int i=0;i<number.size();++i){
        int num = number[i]-'0';
        while(s.size() && s.top() < num){
            if(k==0) break;
            s.pop();
            k--;
        }
        s.push(num);
    }
    
    // 엣지케이스 : k가 남은경우 stk에서 빼준다.
    while(k--){
        s.pop();
    }
    
    while(s.size()){
        answer += to_string(s.top());
        s.pop();
    }
    
    
    
    reverse(answer.begin(),answer.end());
    
//     for(int i=0;i<number.size();++i){
//         pq.push(number[i]-'0');
//         v.push_back(number[i]-'0');
//     }
    
//     for(int i=0;i<k;++i){
//         int num = pq.top(); pq.pop();
//         vis[num]++;
//     }
    
//     vector<int> tmp;
//     for(auto i : v){
//         if(vis[i]){
//             vis[i]--;
//             continue;
//         }
//         tmp.push_back(i);
//     }
    
//     for(auto i : tmp){
//         answer+=to_string(i);
//     }
    
    
    return answer;
}