[Programmers, C++]#Level2_큰 수 만들기, stack 컨테이너, stack, 스택

#1. 문제

프로그래머스

 

 

---

 

#2. 풀이

 

1. deque

[Basic C++] #68_deque

deque은 C++의 STL에서 제공하는 순차 컨테이너로, 컨테이너의 양 쪽 끝에서 접근/삽입/제거 작업이 모두 가능해, 사용자에게 유연함을 제공합니다.

 

2. 주어진 목록의 순서 유지 + 내림차순으로 최대 값 찾기

1. 주어진 수열의 순서를 유지하며 최대 값을 찾기 위해 deque컨테이너를 활용합니다. stack을 활용하면, string을 초기화하기 위한 추가적인 작업이 필요해, 편의상 deque 컨테이너를 활용합니다.
2. 수열의 첫 번째 항목부터 차례대로 순회하며, stack의 top과 비교하고, deque의 back이 더 작다면 pop_back을 수행합니다. 이를 통해, deque에 저장한 숫자들을 front->back 순서의 오름차순을 유지합니다.
3. 마지막으로, k개의 숫자를 모두 제거하지 못했다면, stack에 쌓여있는 숫자들을 남은 k만큼 pop_back()해주고, deque 컨테이너를 통해 string을 초기화하여 이를 결과 값으로 반환합니다.

 

---

 

#3. 코드

/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/42883
    @문제: 주어진 숫자에서 k개의 수를 조합하여 가장 큰 수가 나오는 경우 문자열로 반환
    @설명
        1. 숫자의 순서를 유지한 상태에서, k개를 제거하여 최대 값을 나타낼 수 있는 경우 반환
        2. stack활용, stack을 채워가며 s.top() 과 number[i]의 비교, 그리고 k개가 정상적으로 제거 되었는지 체크
*/

//@그리디 알고리즘, 통과

#include <string>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

string solution(string number, int k) {

    deque<char> s;

    for(int i=0; i<(int)number.size(); ++i)
    {
        while(!s.empty() && s.back() < number[i] && k > 0)
        {
            s.pop_back();
            k--;
        }
        s.push_back(number[i]);
    }

    while(k>0)
    {
        s.pop_back();
        k--;
    }

    string ans(begin(s), end(s));

    return ans;
}

 

---