[Programmers] Lv2. 큰 수 만들기 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

처음에는 너무 쉬운데? 하면서 내림차순으로 정렬 후 뒤의 숫자 k개를 제거하는 방식으로 풀었으나, 문제를 제가 잘못 이해했더라구요. 기존에 주어지는 number 수들은 기존 위치를 지켜야 했습니다. 예제 2번의 "1231234"를 예시로 들면,

// 제거할 숫자에 '|'표시
 || |
"1231234"  -> "3234"

 

결과로 나온 "3234"는 기존과 같이 똑같은 순서를 유지하고 있다는 겁니다. 이런 방식으로 풀어야 했네요.

그래서 저는 스택(Stack)을 이용해서 제거하고 남은 숫자들만 담아두려고 했습니다. 그런데, 스택은 뒤에서 밖에 못 빼니까 문자열 생성이 거꾸로 되니, 데크(deque)를 대신 이용했습니다.

 

 

방법은 다음과 같습니다.

 

• deque가 비었거나, 현재 숫자가 deque의 마지막 숫자(back)보다 작거나 같을 경우, deque에 삽입합니다.
• 그게 아니라면, 다음 조건들 중 하나라도 만족하지 않을 때까지 deque의 back을 pop해주고, k를 감소시킵니다.
  • deque가 비어 있지 않을 경우
  • deque의 마지막 숫자(back)가 현재 숫자보다 작을 경우
  • k가 0보다 클 경우 
• 위 pop 연산이 끝난 후에는 현재 숫자를 deque에 삽입합니다.
• 위의 루프가 다 끝난 후, k가 0 이상이라면 deque의 뒷 숫자들을 k개만큼 제거해줍니다.
  • k가 0 이상인 채로 루프가 끝났다는 것은 숫자가 내림차순으로 되어 있었다는 말입니다.
  • 그렇기에, 뒤에서부터 제거해주면 가장 큰 숫자가 됩니다.
• 위의 모든 연산이 끝났다면, deque에 남아 있는 숫자들을 문자열로 리턴합니다.

 

✏️소스 코드 및 결과

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

string solution(string number, int k) {
    deque<char> selectedNums;
    int removeCount = k;

    for (const auto& num : number)
    {
        if (selectedNums.empty() or num <= selectedNums.back()) {
            selectedNums.emplace_back(num);
            continue;
        }

        while (!selectedNums.empty() and (selectedNums.back() < num) and (removeCount > 0)) {
            removeCount--;
            selectedNums.pop_back();
        }

        selectedNums.emplace_back(num);
    }

    /*
        - 내림차순으로 정렬된 number의 경우, removeCount를 다 소모하기 전에 for문이 끝남
        - 따라서, 해당 removeCount만큼 뒷 숫자를 제거
    */
    for (int i = 0; i < removeCount; i++)
        selectedNums.pop_back();
    return string(selectedNums.begin(), selectedNums.end());
}