Programmers [탐욕법 Greedy] : 큰 수 만들기 풀이 및 코드

programmers.co.kr/learn/courses/30/lessons/42883?language=cpp

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

풀이에 따라 시간이 확연하게 차이나는 큰 수 만들기 문제

주어진 숫자에서 k개의 숫자를 제거했을 때 가장 큰 수를 반환해야 한다

하지만 정석적으로 N자리의 숫자 중 K개를 제거하는 경우를 모두 구하면 아래 사진의 오른쪽 위와 같은 공식이 나온다

그렇기에 최대 백만자리에서는 시간초과가 날 수 밖에 

그렇기 때문에 다음과 같이 풀어줬다

len = number의 length - k (목표 문자열 길이)라고 했을 때,

① number내의 모든 문자를 탐색하면서 현재 인덱스부터 뒤에서 len개만큼 확인하면서 최댓값을 구한다

② 구한 최댓값을 answer에 push하고 해당 문자열의 index를 현재 index로 한다

③ 그리고 숫자의 최댓값은 9이기 때문에 9가 처음 나오면 바로 2번을 수행해준 뒤 break해준다

 

예제의 4177252841에서는 4개를 제거하면 결과적으로 6자리의 숫자가 나와야 한다

- 417725 중 최댓값인 세번째 7을 answer에 push한 후 인덱스=3(+1)

- 725 (뒤에서 4개는 접근X) 중 최댓값인 7을 push한 후 인덱스 = 4(+1)

와 같이 실행하면, 결과값인 775841이 나온당

 

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
	string answer = "";
	int len = number.length() - k;
	for (int i = 0; i < number.size(); i++) {
		if (!len)break;
		int n=number[i]-'0',index=i;
		for (int j = i+1; j <= number.size() - len; j++) {
			if (number[j] - '0' > n) {
				n = number[j] - '0';
				index = j;if(n==9)break;
			}
		}
		answer.push_back(n + '0');
		i = index; len--;
	}
	return answer;
}

dfs로 풀면 O(k∑nPi)로 매우매우매우 크지만, 위와 같이 풀면 O(n^2)로 해결할 수 있당