[백준 2812] 크게 만들기

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

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

int N, K;
string in_str;
string ans;

stack<int> stk;


void input()
{
	cin >> N >> K;
	cin >> in_str;
}

void get_max()
{
	int cnt = K;
	for (int i = 0; i < N; i++) {
		while (!stk.empty() && cnt > 0 && stk.top() < in_str[i] - '0') {
			stk.pop();
			cnt--;
		}
		stk.push(in_str[i] - '0');	// 문자에서 숫자로 바꿔서 푸시
	}
}

void output()
{
	while (!stk.empty()) {
		ans += stk.top() + '0';	// 숫자에서 문자로 바꿔서 팝
		stk.pop();
	}
	reverse(ans.begin(), ans.end());
	for (int i = 0; i < N - K; i++) cout << ans[i];
}


int main()
{
	input();
	get_max();
	output();
	return 0;
}

않이.. 이 문제 당연히 조합 아니냐고.. 

는 했다가 타임아웃 났다..(조합적 폭발, 그렇게 모든 경우의 수 탐색하는 문제 아님ㅋ) 심지어 전에 풀어본 문제임. 찾아보면 블로그에 파이썬 코드도 있음... 나레기 이번엔 한번에 풀지 못했지만 다음엔 한번에 풀어버릴거다. 

이문제는 스택이다 스택 !

 

// get_max( ) 함수

사실 deque로 풀어도 되지만 나는 stack이 좀 더 친근하므로... 그리고 이 문제는 스택을 사용해도 28ms밖에 안나오닉까... 

입력받은 문자열을 한 문자 단위로 쪼개서 스택의 가장 윗부분과 비교한다. 

만약 가장 윗 부분의 숫자보다 현재 탐색하고 있는 숫자가 크면, (가장 큰 수를 만들어야 하기 때문에 맨 앞자리가 크면 클 수록 좋음) 스택 안에 있는 모든 원소를 pop 시킨다. 그리고 해당 숫자를 스택에 push하는데, 이때 비교의 용이성을 위해 int(char - '0')로 바꿔서 삽입했다. 

이 과정을 문자열의 마지막 문자까지 반복한다. 이 과정에서 cnt == 0이 되면 더이상 문자를 지우지 않고 스택에 삽입한다. 

 

 

// output( ) 함수

현재 스택에 들어있는 숫자를 pop하면, 우리가 구해야할 숫자의 반대 순서로 출력된다. 

예컨대 예제 1번의 경우 다음과 같다. 

// input
4 2 
1924

// target
94

// stk.pop()
49

따라서 문자열을 한번 뒤집어 주는 과정이 필요하다. 이를 위해 스택에 들어있는 원소를 하나씩 pop하여 ans 문자열에 더해주었다. 그리고 해당 문자열을 <algorithm>의 reverse 라이브러리를 사용하여 뒤집어 주었다. 

마지막으로 해당 문자열의 0부터 N - K - 1번째 문자까지 출력하여 (N개의 숫자 중 K개를 지워야 하므로) 답을 도출하였다.