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

문제

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

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

 

 

문제풀이

 

스택의 느낌으로 문제를 풀었다.

number의 크기만큼 반복문을 돌면서, 현재 해당하는 숫자를 answer에 더하기 전에

answer의 맨 뒤에 있는 숫자보다 큰 숫자를 만나면 조건을 판단한다.

현재 해당하는 숫자를 포함한 남은 개수가 만들어야 되는 target_size보다 크다면 answer의 끝 숫자를 삭제한다.

 

그다음 조건에 맞지 않아 반복문이 종료됐으면 현재 숫자를 answer의 끝에 더해준다.

반복문이 종료됐을 때 만약 answer의 크기가 target_size보다 크다면 target_size의 크기가 될 때까지 answer의 끝을 제거해 준다.

 

코드

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

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

    int target_size(number.size() - k);
    for (int idx = 0; idx < number.size(); ++idx) {
        int rest_cnt = number.size() - idx;
        while (!answer.empty() && answer.back() < number[idx] && answer.size() + rest_cnt > target_size) {
            answer.pop_back();
        }
        answer += number[idx];
    }

    while (answer.size() > target_size) {
        answer.pop_back();
    }

    return answer;
}