백준 2812 c++ "크게 만들기" -PlusUltraCode-

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

 

 

[필자 사고]

조심해야 될 부분이 많은 문제였다.

일단 필자는 처음에는 이 문제를 풀 때 stack을 이용해서 탐욕적으로 문제를 접근하는 방식으로 해결했다.

처음 필자가 간과했던 점은 무한루프가 되는 조건이 있었는데 그 부분을 break을 빼먹었다.

다음으로 조심해야 될 부분은 K가 없엉지지 않았는데 작업이 끝나는 경우를 고려하지 않았따.

K가 남아있을경우는 마지막 숫자들을 제거해줘야 한다. 

다음은 자세한 코드 해설이다.

[코드 해설]

🔹 Input() 함수

• 사용자로부터 입력을 받는 함수입니다.
• 첫 번째 줄에서 숫자의 전체 길이 N과 제거해야 할 숫자의 개수 K를 입력받습니다.
• 두 번째 줄에서 숫자 문자열을 입력받아 str 변수에 저장합니다.

---

🔹 Game_Start() 함수

이 함수는 핵심 로직을 수행하며, 아래의 절차로 동작합니다:

1. 시작 인덱스 초기화
   • startIdx = 0으로 설정하여 숫자 문자열의 처음부터 탐색을 시작합니다.
2. 숫자 문자열을 순회하면서 큰 수를 만들기 위한 처리
   • 아직 모든 문자를 탐색하지 않았고, 제거할 기회 K가 남아 있는 동안 반복합니다.
   • 스택이 비어 있다면 현재 문자를 스택에 넣고 다음 인덱스로 넘어갑니다.
   • 그렇지 않다면, 스택의 가장 위에 있는 문자(myStack.top())와 현재 문자를 비교합니다.
     • 만약 현재 문자가 더 크다면, 스택의 위에 있는 문자를 제거(pop)하고 K를 1 줄입니다.
     • 그렇지 않으면 비교를 멈추고 현재 문자를 스택에 넣습니다.
   • 이 과정을 통해 작은 숫자들을 제거하고 더 큰 숫자들이 앞에 오도록 합니다.
3. 남은 문자를 그대로 스택에 넣기
   • 위 반복이 끝난 후에도 아직 문자열에 남아있는 문자들이 있다면, 그 문자들은 그대로 스택에 추가합니다.
4. 스택에 남은 문자를 꺼내서 정답 출력
   • 스택은 후입선출 구조이므로, 스택에서 문자를 하나씩 꺼내서 벡터에 거꾸로 저장합니다.
   • 그런 다음 벡터를 뒤에서부터 출력하여 최종 결과를 만듭니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;

int N, K;
string str;
stack<char> myStack;
void Input() {
	cin >> N >> K;
	cin >> str;

}

void Game_Start() {
	
	int startIdx = 0;
	
	while (startIdx < N && K>0) {
		if (myStack.empty()) {
			myStack.push(str[startIdx++]);
			continue;
		}

	
		while (!myStack.empty()&&K>0) {
			if (myStack.top() < str[startIdx]) {
				myStack.pop();
				K--;
			}
			else {
				break; // 여기 빠져나와야 다음 글자를 볼 수 있음
			}
		}
		myStack.push(str[startIdx++]);
		
	}
	for (int i = startIdx; i < N; i++) {
		myStack.push(str[i]);
	}

	vector<char> arr;
	while (!myStack.empty()) {
		arr.push_back(myStack.top());
		myStack.pop();
	}

	for (int i = arr.size() - 1; i >= 0; i--) {
		cout << arr[i];
	}
}

int main(void) {
	Input();
	Game_Start();
}