[G4] 백준 1662번 압축 C++ 스택

리뷰

 

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

오랜만에 풀어본 스택 문제, 역시 스택 문제는 머리만으로 풀려고 하지 말고 디버깅이나 직접 그려가며 풀어야 하는 것 같다.

 

 

전역 변수

• s : 압축되지 않은 문자열을 저장할 변수
• Cstack : 문자 스택 정보를 저장할 변수
• Nstack : 정수 스택 정보를 저장할 변수(초기 크기 1, 값 0)

 

함수

없음

 

 

문제풀이

1. s를 입력 받고, s를 뒤에서 부터 탐색하는 for문을 개행해 준다.
2. 만약 현재 문자가 ')'라면 Nstack에 0을 추가해 준다.
3. 만약 현재 문자가 '('라면 Cstack에 '('를 추가해 준다.
4. 만약 현재 문자가 정수형 문자라면 두 가지 조건으로 나누어 로직을 처리해 준다.
5. 먼저 Cstack이 비지 않았다면('('가 존재 한다면) Cstack에서 요소를 하나 빼내어 준다.
6. Nstack의 가장 뒤 숫자에 정수 문자만큼 값을 곱해준 뒤 해당 값을 res에 저장해 준다.
7. Nstack에서 요소를 하나 빼낸 후 가장 뒤에 있는 요소에 res를 더해준다.
8. 만약 Cstack이 비었다면 Nstack의 가장 뒤에 있는 요소에 1만큼 값을 증가시킨다.
9. 모든 요소를 순회한 후에 Nstack의 0번 인덱스 요소에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 정수형 벡터를 사용하지 않고 변수 len을 사용해 정답을 구했지만 Fail을 받았다.
2. 정수형 벡터를 추가 해서 각 압축 상태를 체크해 주어 AC를 받았다.

 

참고 사항

• ')'가 나왔을 땐 정수형 스택에 0을 푸시하여 압축 값을 명시해 준다.
• '('가 나왔을 땐 C스택에 '('를 넣어 압축이 끝나는 시점임을 명시해 준다.
• 숫자가 나왔을 땐 Cstack이 비지 않았다면 압축값에 곱하기를, 비었다면 압축값에 더하기를 해주면 된다.
• 압축값에 곱하기를 진행하였다면 괄호가 닫힌 것이므로 Nstack의 크기를 줄여주어야 한다.

 

정답 코드

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

string s, Cstack;
vector<int> Nstack(1, 0);

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

	cin >> s;
	for (int i = s.size() - 1; i >= 0; --i) {
		if (s[i] == ')') {
			Nstack.push_back(0);
		}
		else if (s[i] == '(') {
			Cstack.push_back(s[i]);
		}
		else {
			if (!Cstack.empty()) {
				Cstack.pop_back();
				Nstack.back() *= s[i] - '0';
				int res = Nstack.back();
				Nstack.pop_back();
				Nstack.back() += res;
			}
			else Nstack.back()++;
		}
	}
	cout << Nstack[0];
}