[C++][프로그래머스] level 2 - 큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

CODE

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    vector <int> v;
    int temp = k;
    
    for(int i=0;i<number.size();i++){
        int cur = number[i]; //현재 넣고 싶은 숫자
        
        if ((temp == 0) || (v.empty())){  //더 빼지 않아야 할 때
            v.push_back(cur);
            continue;
        }
        int size =  v.size();
        for(int j=0;j< size;j++){  //size 자리에 바로 v.size()를 넣으면 원하는 만큼 반복문을 돌지않음
            if ((v.back() < cur) && (temp > 0) && (!v.empty())){
                v.pop_back();
                temp--;
            }
            else  {
                break;
            }
        }
        v.push_back(cur);
    }

    for( int i=0 ; i < number.size() - k ; i++ ){
        answer += v[i];
    }
    
    return answer;
}

+코드 설명

stack에 cur ( = number[i])를 하나씩 넣는 과정중에서
case 1 :   k(뺄 수 있는 횟수)가 0일때    or    vector가 비어있을 때
⇒ vector에 cur를 push_back한다

case 1 : k가 0이 아닐 때  and  vector가 비어있지 않을 때    and    vector의 가장 마지막 수보다 cur가 클 때
⇒ vector의 가장 마지막 수보다 cur가 작아질 때까지
    Q : v.pop_back();
            temp--;
      Q를 반복하고 가장 마지막에 cur값을 vector에 push_back한다

 

필요한 개념  & 문제 요구사항

+필요한 개념

[C++] vector - 벡터 개념정리

+유의사항

size 자리에 바로 v.size()를 넣으면 v.pop_push()를 수행하게 될때마다 v.size()가 바뀌어
원하는 만큼 반복문을 돌지않게 되는 문제가 발생!!하므로 유의하세요 (이거때문에 저는 1시간 버림...ㅠ)

+출처

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