[알고리즘/프로그래머스] 큰 수 만들기 - C++

이번에도 탐욕법(그리디)를 이용한 문제를 풀어보고자 한다.

*본인은 C++로 코딩할 예정이다.

---

1. 문제

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

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

이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다.

number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중

가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

출저 - 프로그래머스

2. 사고 - 탐욕법

1. number의 배열을 순회하며 하나씩 이전 숫자와 비교한다.

2. 큰 숫자가 나타날 경우 그 숫자보다 작은 숫자들을 pop하고, 그 만큼 k를 감소시킨다.

3. k가 0이 되면 남은 숫자들을 자릿수에 맞춰서 반환한다.

4. k가 0이 되지않을때 역시 고려한다.

3. 코딩

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

string solution(string number, int k) {
	string answer = "";
	int len;
	for (unsigned int i = 0; i < number.size(); i++) {
		len = answer.size();
		for (int j = 0; j < len; j++) {
			if (answer[j] < number[i]) {
				answer.pop_back();
				k--;
			}
			if (k == 0) {
				break;
			}
		}
		if (k == 0) {
			answer += number.substr(i, number.size());
			break;
		}
		answer += number[i];
		//cout << "answer : " << answer << ", k : " << k << endl;
	}
	answer = answer.substr(0, answer.size() - k);
	return answer;
}

int main(void) {
	string number = "4177252841";
	int k = 4;

	cout << solution(number, k) << endl;

	return 0;
}

- 수 : "4177252841"

- 뺄 갯수 : 4개

= 결과 : 775841

4. 알게된 것

string의 substr()함수!

아주 유용한 함수이다. 지정한 위치부터, 지정한 위치까지의 값을 뽑아낼 수 있는데, 유용하게 쓰인다.

파이썬의 슬라이싱과 비슷하다 보면 된다.

해당 함수를 이용해 k가 순환 중에 0이 안나오는 경우까지 고려하여 코딩해야한다.

이러한 과정을 거치면 문제를 해결 가능하다.

 

---

왜 초기화 코드에 vector가 있었던걸까?