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

프로그래머스

[문제 설명]

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

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

입출력 예

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

---

[문제 풀이]

문제를 푸는데 적용한 방법은 아래와 같다.

 

1. 현재 숫자보다 뒤에 있는 수가 크다면 현재 숫자를 지운다.

2. 지운 숫자의 개수를 카운트하여 입력으로 들어온 k와 같다면 현재 문자열을 return한다.

3. 지운 숫자의 개수가 k보다 작다면 1번으로 돌아간다.

4. 만약 4321과 같이 앞 숫자가 뒷 숫자보다 계속 크다면, 뒤에서부터 k개를 지워준다.

 

처음 문제를 풀 때 4번과 같은 경우를 고려하지 않았어서 문제를 틀렸었다.

테스트 케이스를 생각해내는게 정말 어려운 일인것 같다..

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

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

string solution(string number, int k) {
    string answer = "";
    int count = 0;
    auto iter = number.begin();
    
    for(iter; iter != number.end();)
    {
        if(*iter < *(iter+1))
        {
            number.erase(iter);
            iter = number.begin();
            count++;
            
            if(count == k) break;
        }
        else
        {
            ++iter;
        }
    }
    if(count != k)
    {
        number.erase(number.end() - (k-count), number.end());
    }
    return number;
}