Programers 큰 수 만들기

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

프로그래머스

프로그래머스 큰 수 만들기 문제입니다.

 

아이디어

Greedy문제입니다. 큰 수를 만들기 위한 전략을 로직으로 녹여내는 것이 중요한데, 본인은 앞에서 부터 가장 큰 수를 찾고 작은 수들은 걸러내는 방식을 사용했습니다.

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

string solution(string number, int k) {
	int cnt = k;
	int maxPos = 0;
	int start = 0;
	string answer = "";
	while (cnt>0) {
		int frontMax = 0;
		int cnt2 = cnt;
		if (answer.length() + cnt == number.length()) break;
		//앞에서 가장 큰수를 찾는다
		for (int i = start; cnt2>=0; cnt2--,i++) {
			if (frontMax<int(number[i])) {
				frontMax = int(number[i]);
				maxPos = i;
			}			
		}
		cnt -= (maxPos - start);
		answer += number[maxPos];
		if (cnt == 0 && (number.length() - answer.length() != k)) answer += number.substr(maxPos + 1);
		start = maxPos+1;
	}
	return answer;
}