[G3] 백준 2812번 크게 만들기 C++ 스택, 문자열, 그리디 알고리즘

리뷰

 

수를 문자열로 변환하여 스택을 활용한 그리디 문제이다.

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

 

전역 변수

• lst : 숫자를 저장할 문자열 변수
• n, k, cnt : 숫자의 길이 n, 지울 숫자의 개수 k, 지운 숫자를 체크할 변수 cnt

 

함수

없음

 

 

문제풀이

1. n, k, lst값을 순서대로 입력 받아주고, 스택으로 사용할 문자타입 벡터 s를 초기화 해준다.
2. n번의 반복문을 개행하고, s가 비지 않았고, s의 back이 현재 수보다 작으며, cnt가 k보다 작다면 문자열을 제거한다.
3. 문자열이 제거된 후에는 cnt를 증가시켜서 k와 비교를 해주어야 한다.
4. 위 작업이 끝난 후에는 스택에 현재 숫자(문자)를 추가해 준다.
5. 최종적으로 스택에 저장되어 있는 숫자(문자)를 한개씩 출력해 주면 된다. (공백 구분x)

 

참고 사항

숫자의 앞에서 부터 탐색하며 더 큰 값이 들어왔을 경우 치환해주는 형식이다.

 

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;
string lst;
int n, k, cnt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k >> lst;
	vector<char> s;
	for (int i = 0; i < n; i++) {
		while (!s.empty() && s.back() < lst[i] && cnt < k) {
			cnt++;
			s.pop_back();
		}
		s.push_back(lst[i]);
	}
	for (int i = 0; i < n - k; i++) cout << s[i];
}