프로그래머스 큰 수 만들기

순서가 바뀌어지는 것이 아닌 나열된 숫자에서 순서를 지키면서 찾는 것이다. 가장 큰 수를 만들기 위해선 앞자리부터 큰 값을 유지해야 한다. 순서를 지키면서 유지해야기 때문에 stack 자료구조를 이용한다

 

마지막에 지워야 할 k가 남아있으면 뒤에서부터 작은 값이기 때문에, 뒤에서부터 그 개수만큼 pop을 한다

 

문제: https://programmers.co.kr/learn/courses/30/lessons/42883

깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_큰_수_만들기.cpp

 

	#include <stack>
	#include <string>
	#include <vector>
	using namespace std;
	string solution(string number, int k) {
	string answer = "";
	int len = number.length();
	stack<char> st;
	for (int i = 0; i < len; i++) {
	char num = number[i];
	while (!st.empty() && k > 0) {
	char tp = st.top();
	if (tp < num) {
	st.pop();
	k--;
	}
	else {
	break;
	}
	}
	st.push(num);
	}
	while (k > 0) {
	st.pop();
	k--;
	}
	while (!st.empty()) {
	answer = st.top() + answer;
	st.pop();
	}
	return answer;
	}

view raw Programmers_큰_수_만들기.cpp hosted with ❤ by GitHub