[프로그래머스] Level.2 연습문제-큰 수 만들기

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

 

 

문제설명

 

제한조건

 

입출력예

 

첫번째풀이-10번 시간초과

이렇게 풀기는 했는데 아무리봐도 이렇게 푸는게 아닌것 같다...

일단 8번문제가 200ms뜨더라 엄청 긴 number가 주어지는것 같은데 그럴때는 다른 풀이법을 생각해야한다 ㅠㅠ

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
	string answer = "";
	vector<int>st;
	
	for (int i = 0;i < number.size();i++)
		st.push_back(number[i] - '0');

	int tmp = st[0];

	for (;;) {
		if (k == 0) break;
		int idx = 0;
		for (;;) {
			if (tmp < st[idx]) {
				st.erase(st.begin() + idx - 1);
				idx--;
				k--;
				tmp = st[idx];
				break;
			}
			else if (st[idx] < tmp&&st[idx] < st[idx + 1]) {
				st.erase(st.begin() + idx);
				k--;
				break;
			}
			else idx++;
		}
	}

	for (int i = 0;i < st.size();i++) {
		answer += st[i] + '0';
	}
	return answer;
}

 

 

 

 

두번째풀이 성공

 

시간초과를 해결할 방법이 떠오르지 않아서 다른사람들의 풀이를 참고해서 풀었다....

나는 왜 이런 풀이를 생각하지 못할까 ㅠㅠㅠㅠㅠ하 현타..

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

string solution(string number, int k) {
	string answer = "";
    int idx = -1;
    for(int i=0; i<number.size()-k; i++){
        char max = ' ';
        for(int j=idx+1; j<=k+i; j++){
            if(max < number[j]){
                max = number[j];
                idx = j;
            }
        }
        answer += max;
    }
	return answer;
}