[Programmers] - 큰 수 만들기

문제

탐욕법 문제인데 그걸 생각하지 않고 해봤다.

코드

#include <string>
#include <stack>

using namespace std;

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

	stack<char> s;
	
	int i = 0;
	for (int j = 0;j < number.length();j++) {
		while (!s.empty() && s.top() < number[i]){
			s.pop();
			k--;
			if (k == 0) {
				while (i <= number.length() - 1) {
					s.push(number[i]);
					i++;
				}
			}
		}
		if (k == 0) break;
		
		s.push(number[i]);
		i++;
	}
	while (k--) s.pop();//"4321" 같은 경우도 있기 때문에

	while (!s.empty()) {//join
		answer = s.top() + answer;
		s.pop();
	}
	return answer;
}

요약

• stack을 이용해서 풀어보았다.
• number의 자릿수가 커지면 시간이 엄청 길어진다.
• 또다른 알고리즘이 생각 안난다.