[프로그래머스/C++] 큰 수 만들기 - 탐욕법(Greedy)

• 큰 수 만들기

문제 설명

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

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

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

제한 조건

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

입출력 예

 

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

---

💡 그리디 (Greedy)

그리디는 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 말한다.

매 순간 가장 좋아보이는 것을 선택하고, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.

 

 그리디는 단순 암기가 아닌 창의력을 요구하는 문제 유형이 많기 때문에 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 필요하다.

 

대체로 정렬 알고리즘과 짝을 이뤄 출제되고, 문제에서 "가장 큰 순서대로" 혹은 "가장 작은 순서대로"와 같은 기준을 알게 모르게 제시한다.

 

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민
⇒ 찾을 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 고민

---

나는 이 문제를 처음 풀 때 문자열을 내림차순으로 정렬한 뒤,  왼쪽에서 오른쪽으로 진행하며 오른쪽 수가 더 큰 경우 왼쪽 수를 지우기만 하면 되는 줄 알았다...!

 

최종적인 풀이는 아래와 같다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

string solution(string number, int k) {
	stack<char> st;
	string str = "";
	bool isPoped = false;

	st.push(number[0]);

	for(int i = 1; i < number.size(); i++)
	{
		if(st.top() < number[i])
		{
			while (!st.empty() && st.top() < number[i] && k > 0)
			{
				st.pop();
				isPoped = true;
				k--;
			}
		}
		st.push(number[i]);

		if (k <= 0)
		{
			if (i == number.size() - 1) break;
				
			for (int j = i+1; j < number.size(); j++)
				st.push(number[j]);

			break;
		}
	}

	if (!isPoped)
		return number.substr(0, number.size() - k);
	
	while(!st.empty())
	{
		str += st.top();
		st.pop();
	}
	reverse(begin(str), end(str));

	return str;
}

 

스택을 이용하여 문제를 풀이하였다.

숫자의 순서대로 스택에 넣으면서, 스택의 Top과 현재 인덱스의 char를 비교하며 Top보다 더 큰 수가 나왔을 때, 스택의 Top이 더 작아질때까지 스택의 요소를 Pop으로 삭제한다.

 

Pop으로 스택 요소를 삭제할때마다 k-- 를 진행하여 삭제할 수 있는 개수 k를 지켜야한다.

 

string = "9437227", k = 4 를 예시로 들어보면 

* stack = [9], char = "437227" 를 두고 비교했을 때 stack의 Top인 9가 char의 4보다 더 크기때문에 그냥 넘어가고 4를 다음 stack에 삽입한다.

* stack = [9, 4], char = "37227" 를 두고 비교했을때도 4 < 3 = false이므로 넘어가고 3을 넣는다.

* stack = [9, 4, 3], char = "7227" 를 비교하면 3 < 7 = true 이므로 3을 삭제한다. 이후 k-- 이므로 k = 4->3

* stack = [9, 4], char = "7227" 를 또 비교하면 4 < 7 = true 이므로 4를 삭제한다. 이후 k-- 이므로 k = 2

* stack = [9], char = "7227" 를 비교했을땐 9 < 7 = false이므로 넘어가고 7을 넣는다.

* stack = [9, 7], char = "227" 를 비교했을 때 7 < 2 = false이므로 넘어가고 2를 넣는다.

* stack = [9, 7, 2], char = "27" 를 비교했을 때 2 < 2 = false 이므로 넘어가고 2를 넣는다.

* stack = [9, 7, 2, 2], char = "7" 를 비교했을 때 2 < 7 = true 이므로 2를 삭제한다. 이후 k-- 이므로 k = 1

* stack = [9, 7, 2], char = "7" 를 비교했을 때 2 < 7 = true 이므로 2를 삭제한다. 이후 k-- 이므로 k = 0

* stack = [9, 7], char = "7"를 비교했을 때 7 < 7 = false 이므로 넘어가고 7을 넣는다.

* stack = [9, 7, 7]

 

이후, stack 에 있는 char 들을 string 변수에 += top() 으로 저장한 뒤, 스택의 특성상 문자열이 뒤집어져 출력되므로 reverse 함수로 뒤집어준다.

---

참조

https://velog.io/@bbirong/%EC%9D%B4%EA%B2%83%EC%9D%B4-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%8B%A4-%EA%B7%B8%EB%A6%AC%EB%94%94

1-1. Greedy 개념 & 실전 문제