크게만들기 - C++

문제 바로가기

해당 문제는 그리디 문제이다.

4177252841

숫자를 크게만들려면 단 하나의 조건만 고려하면된다.

앞자리가 뒷자리보다 크면된다.

고로 뒷자리에 뭐가 오던지 상관없이 그냥 앞자리가 크게 숫자를 빼주면 되기 때문에 그리디 문제가 되겠다.

맨처음에는 일단 비교할 숫자가 없으니까 4를 넣는다.

1을 앞자리와 비교한다. => 작으면 넣는다. 41

7을 앞자리와 비교한다 => 1보다 크므로 1을 빼고 7을 넣는다.
7을 앞자리와 비교한다. -> 4보다 크므로 4를 빼고 7을 넣는다.

만약 숫자가 동일하다면 그냥 넣는다. 77

이렇게 과정을 거친후에
더 뺴야할 숫자가 있다면 뒷자리부터 뺸다.

왜냐하면 해당 과정을 거친후에는, 내림차순으로 숫자가 정렬되어있다는것이 보장되어있기 때문에 뒤에서부터 빼면된다.

98824521 에서 3개를 빼야하면 위의 과정을 거치면
988521
이 되고, 오름차순으로 정렬되었음이 명확하므로
988521에서 1을 빼면된다.

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

int main() {
	int N = 0;
	int K = 0;
	string n = "";

	cin >> N;
	cin >> K;
	cin >> n;

	stack<char>c;

//각 숫자를 비교할것이다.
	for (int i = 0; i < n.size(); i++) {
		char f = n[i];
        //만약에 더이상 빼지 못하면 무조건 넣으면 된다.
		if (K == 0) {
			c.push(f);
		}
		else {
        //비어있다면 뺄게 없으니까 넣으면 된다.
			if (c.size() == 0) {
				c.push(f);
			}
			else {
            //비어있지 않은경우
            //내가 더 작으면 넣는다.
				if (c.top() - '0' > f - '0') {
					c.push(f);
				}
                //내가 더 크면, 나보다 큰놈이 나올때까지 뺀다. 만약에 더이상 뺄게 없으면 자기를 넣고 마무리
				else if (c.top() - '0' < f - '0') {
					while (1) {
						if (c.size()>0&&c.top() - '0' < f - '0' && K > 0) {
							c.pop();
							K--;
						}
						else {
							c.push(f);
							break;
						}
					}
				}
                //값이 동일하면 그냥 넣기
				else {
					c.push(f);
				}
			}
		}
	}
    //빼야할게 남았으면 뒤에서 부터 빼기
	for (int i = 0; i < K; i++) {
		c.pop();
	}
	stack<char>tt;

	while (c.size() > 0) {
		tt.push(c.top());
		c.pop();
	}
//거꾸로 해서 출력
	while (tt.size() > 0) {
		cout << tt.top();
		tt.pop();
	}
	return 0;
}

리팩토링 코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0;
	int K = 0;
	string n = "";

	cin >> N;
	cin >> K;
	cin >> n;

	stack<char>c;

	for (int i = 0; i < n.size(); i++) {
		char f = n[i];
		while (c.size() > 0 && c.top() - '0' < f - '0' && K > 0) {
			c.pop();
			K--;
		}
		c.push(f);
	}

	for (int i = 0; i < K; i++) {
		c.pop();
	}

	stack<char>tt;

	while (c.size() > 0) {
		tt.push(c.top());
		c.pop();
	}

	while (tt.size() > 0) {
		cout << tt.top();
		tt.pop();
	}
	return 0;
}