[프로그래머스/C++] 큰 수 만들기

(6/24 - X)

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

코딩테스트 연습 - 큰 수 만들기

 

 

처음에는 min_element를 이용해서 푸는 방법을 떠올렸는데 3번 테스트 케이스에서 적용되지 않는 식이었다. 다음으로는 실제 값에다 자릿수의 값으로 보정 값을 줄까 생각해 봤는데 이 또한 틀린 풀이였다. 해결 방법 자체가 떠오르지 않았다. 그래서 계속 고민하다가 구글링 해서 힌트를 얻었다. 테스트 케이스마다 신경 써 줘야 할 것이 많아서 까다로웠다.

 

구현

스택을 이용한다.

 

0. numbers를 순회하면서 1-2를 반복한다.

1. 스택이 비어 있지 않고, k가 0보다 크며, c - '0'가 스택의 top보다 클 경우 이 조건을 하나라도 만족하지 않을 때까지 1.1와 1.2 반복

1.1 top을 pop 한다.

1.2 k를 1 감소시킨다.

2. c를 스택에 push 한다.

3. 스택 사이즈가 number.size() - k보다 클 때, top과 top-1의 수를 비교하며 더 큰 수를 top에 넣는다.

 

 

 

참고

케이스 중 "654321" k=1, "654321" k=5, "999" k=2를 테스트 해 보자.

 

코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

string solution(string number, int k) {
    string answer = "";

    int len = number.length();
    int answer_size = len - k;

    stack<int> s;
    for (auto& c : number) { // 0
        while (!s.empty() && k > 0 && c - '0' > s.top()) { // 1
            s.pop(); // 1.1
            k--; // 1.2
        }
        s.push(c - '0'); // 2
    }
    if (s.size() > answer_size) { // 3
        int top = s.top();
        s.pop();
        if (s.top() < top) {
            s.pop();
            s.push(top);
        }
    }

    answer.resize(answer_size);
    for (int i = answer_size - 1; i >= 0; i--) {
        answer[i] = (s.top() + '0');
        s.pop();
    }

    return answer;

}