프로그래머스 - 큰 수 만들기(Level 2)/Wanna Be 컴잘알

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

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스

-문제-

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

-접근법-

문제를 다른 시각으로 보자면 Number.length()-K를 하면 적어도 이만큼의 숫자는 남아있어야한다.

위의 예시에서는 Number.length()-K는 4이다. 4자리 숫자가 남아있어야한다.

그렇다면 마지막 3자리 숫자는 남겨두고 앞에서 가장 큰 수를 1개 뽑으면 최소한 4자리는 만들 수가 있다.

처음에 1231 중에 가장 큰 3을 뽑으면 다음에는 마지막 2자리를 확보해놓고 1,2중에 더 큰 1개를 뽑는다.

그렇게 되면 32가 뽑혔으며 4자리를 충족하기위해서는 34를 그대로 뽑아야한다.

 

종료 조건은 2가지이다. 위와같은 예시에선 k=0이 될때, 종료된다. 다른 종료 조건으로 뽑는 수가 자리 갯수가 될때인데

9999123 같은 경우에서 k=3이면 맨뒤에 123을 지우고 앞에서부터 4개를 뽑으면된다. 이럴경우 k가 줄어들지 않아

9999를 뽑아도 k=3이 유지된다. 내가 숫자를 뽑은 횟수와 내가 뽑아야할 횟수가 동일하면 종료처리를 해주었다.

 

-후기-

 

1. Level 2의 다른 문제들보다는 어려운 것 같다. Level 2.5 느낌?(내가 그리디에 약한거 일 수도...)

2. 표로 그리면서 했으면 더 쉬웠을듯 하다.

3. 똑같은 로직으로 처음엔 재귀함수로 풀었지만 10번 TC에서 시간초과가 나서 재귀로 풀었던걸 whlie문으로 바꾸니 시간초과가 나지 않았다.. 같은 로직으로 돌지만 시간차이가 이렇게 많이나나 싶다.

(찾아보니 같은 로직이여도 함수를 계속 호출함으로써 시간이 더 느려진다고 한다. )

 

-코드-

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

string answer = "";
int jari_cnt = 0;


string solution(string number, int k) {
	jari_cnt = number.length() - k;
	int start = 0;
	int jari = 0;

	while (1) {
		if (jari == jari_cnt) {
			break;
		}
		else if (k == 0) {
			for (int i = start; i < number.length(); i++) {
				answer = answer + number[i];
			}
			break;
		}

		/* 최대값을 기억하기 위한 변수*/
		int max_value = -1;
		int max_index = -1;

		/*몇개의 수를 뺐는지 기억하는 변수*/
		int minus_cnt = 0;

		for (int i = start; i <= start + k; i++) {
			if (max_value < int(number[i]) - 48) {
				max_value = int(number[i]) - 48;
				max_index = i;
			}
		}

		minus_cnt = max_index - start;
		k -= minus_cnt;

		start = max_index + 1;
		jari += 1;

		answer = answer + (char(max_value + 48));

	}

	return answer;
}