[프로그래머스 문제풀이] 27. 큰 수 만들기

나의 풀이

스트링에서 숫자를 하나씩 가져와서 앞의 수가 뒤의 수보다 작을 때 앞의 수를 삭제하고 인덱스를 감소시키는 로직이다.
가져온 수가 첫 자리이면 -1 감소시키고
첫 자리가 아니라면 그 수를 삭제했을 때 양 옆에 있던 수끼리 크기 비교를 또 해야 하기 때문에
i-2만큼 감소시킨다.

🎉완성코드

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
	for (size_t i = 0; i < number.size(); i++)
	{
		if (k == 0)
			return number;

		if (number[i] < number[i + 1])
		{
			number.erase(number.begin() + i);
			--k;
			if (i == 0)
				i = -1;
			else
				i -= 2;
		}
	}
    return number.substr(0, number.size() - k);
}

추천을 많이 받은 풀이

내가 만든 로직보다 더 빠를 수가 없을 거라고 생각했지만 이 로직이 실행속도가 훨씬 더 빠르다.

number.substr(k)를 통해 답으로 나오는 스트링의 자릿 수의 메모리를 미리 확보해두고
k만큼 반복하여 substr로 자른 스트링의 자리마다 비교한다.

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

string solution(string number, int k) {
    string answer = "";
    answer = number.substr(k); 
    for(int i = k-1;i >=0;i--){
        int j = 0;
        do{
            if(number[i] >= answer[j]){
                char temp = answer[j];
                answer[j] = number[i];
                number[i] = temp;
                j++;
            }else{
                break;
            }
        }while(1);
    }



    return answer;
}

큰 수 만들기 문제 링크