BOJ 1662] 압축

[ 1차 시도 ]

[ 원리 ]

1. 숫자와 괄호 모두 스택에 담는다.

2. )가 나오면 (가 나올때까지 pop하면서 temp++

3. (를 pop하고, top의 숫자*temp 만큼 스택에 수 채우기

4. 반복

 

[ 실패 ]

메모리 초과가 떴다...

#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <string>
#include <algorithm>


using namespace std;


stack<char> stk;
string str;
int res = 0;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == ')') {
			int temp = 0;
			while (stk.top() != '(') {
				temp++;
				stk.pop();
			}
			
			stk.pop();
			int a = (int)(stk.top()-'0');
			stk.pop();
			//res+=(temp * a);
			//cout << "temp : " << temp<<" , a : "<<a << endl;
			for (int j = 0; j < a*temp; j++) {
				stk.push('1');
			}
		}
		else {
			stk.push(str[i]);
		}
		

	}
	cout << stk.size();
	
	return 0;
}

 

[ 2차 시도 ]

- 스택에 다시 넣는 대신, temp에 temp*a를 넣어 문자열의 길이를 더해나간다.

- 결과는 반례가 있어 틀렸다.

반례)

2(2)2(2)

answer: 4

output : 6

 

#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <string>
#include <algorithm>


using namespace std;


stack<char> stk;
string str;
int res = 0;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int temp = 0;

	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == ')') {
			
			while (stk.top() != '(') {
				temp++;
				stk.pop();
			}
			
			stk.pop();
			int a = (int)(stk.top()-'0');
			stk.pop();
			temp = temp * a;
			
		}
		else {
			stk.push(str[i]);
		}
		

	}

	while (!stk.empty()) {
		temp++;
		stk.pop();
	}
	cout << temp;
	
	return 0;
}

 

[ 3차시도 ]

- 기존에는 temp가 이어져서 계속되기 때문에 괄호가 끝어지게 되는 경우에는 계산이 안된다.

- 스택에 숫자 대신에 번호면 1을 넣고 '('면 -1을 넣어서 표현하기 로 함.

- 그 대신 만약 '('의 숫자면 그 숫자에 값은 그대로 넣어준다.

 

 

#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <string>
#include <algorithm>


using namespace std;

/*
2(2)2(2)

answer : 4

output : 6
*/

stack<int> stk;
string str;
int res = 0;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	cin >> str;

	for (int i = 0; i < str.length(); i++) {
		if (str[i] == ')') {
			int temp = 0;
			while (stk.top() != -1) {
				temp += stk.top();
				stk.pop();
			}
			stk.pop(); // ( 제거
			temp *= stk.top(); // temp*a
			stk.pop(); // a 제거
			stk.push(temp);
			
			
		}
		else if (str[i] == '(') {
			stk.push(-1);
		}
		else if (i+1<str.length() && str[i + 1] == '(') {
			stk.push((int)(str[i]-'0'));
		}
		else {
			stk.push(1);
		}

	}
	

	int res = 0;
	while (!stk.empty()) {
		res += stk.top();
		stk.pop();
	}
	cout << res;
	
	return 0;
}