Programmers > 코딩테스트 연습 > 탐욕법(Greedy) > 큰 수 만들기

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42883

풀이

level 2 인 것 치고 생각보다 풀기 어려웠던 문제였다.

일단 주어진 숫자에서 k개의 수를 빼 나간다고 가정했을 때 큰 숫자를 만들기 위해서는

앞쪽에 큰 숫자를 배치해야하며 만약 동일한 숫자가 연달아 나온다면

큰 수를 만들기 위해 뒤쪽에 있는 숫자를 빼야함을 알 수 있다.

이런 문제를 해결하기 위해 stack을 써서 이 문제를 해결하였으며

주어진 number를 스택에 쌓으면서 예를들어 첫 예제인 "1924"를 처리한다고 가정하였을 때

일단 첫 숫자인 1을 스택에 쌓고 

다음 숫자인 9 같은경우 스택에 있는 1보다 크기 때문에 1을 제거한 후 9를 스택에 넣으며

다음 숫자인 2 같은 경우 9보다 작기 때문에 그대로 스택에 넣어주고

마지막 숫자인 4는 스택 가장 위에있는 2보다 크기 때문에 2를 제거하고 넣어주는 방식으로 해결하였다.

대충 이런 컨셉으로 문제를 해결하였으며 

만약 해결이 안된다면 아래 풀이와 주석을 통해 정확히 이해하도록 하자.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

string solution(string number, int k)
{
	stack<char> stk;//스택
	int size = number.length() - k; //k개를 뺐을 때 나오는 숫자의 갯수
	for (int i = 0; i < number.length(); i++) //주어진 숫자를 차례대로 처리
	{
		char ch = number[i]; //i번째 문자
		for (; (!stk.empty()) && k > 0; k--) //스택이 비어있지 않고 k가 0보다 클 때 조건문
		{
			char stack_top = stk.top(); //스택 가장 위에있는 수
			if (stack_top >= ch) break;
			//만약 스택 가장 위에있는 수보다 처리하고자 하는 수가 작거나 같으면 break
			stk.pop(); //처리하고자 하는 수가 더 크다면 스택 가장 위에있는 수를 제거
		}
		stk.push(ch); //스택에 push
	}

	while (stk.size() != size) stk.pop();
	//처음혹은 중간부터 같은 수가 연달아 나왔을 때 ex) number = 10000 , k = 2 인 경우
	//위의 방식으로는 해결되지 않는 경우가 있으므로 
	//size가 될 때까지 스택을 제거한다.

	string answer;
	while (!stk.empty()) //answer 추출
	{
		char x = stk.top();
		answer = x + answer;
		stk.pop();
	}
	return answer;
}