[백준 / C++] 1662번: 압축

 

 

 

 

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

1662번: 압축

 

난이도: solved.ac 골드 5

 

손으로 이 문제를 푼다고 하면, 길이를 계산할 때 가장 안쪽 괄호부터 개수를 세어서 계산한다.

따라서 i 겹의 괄호 안에 몇 개의 숫자가 있는지를 저장하는 len이라는 배열을 만들었다.

 

편의상 괄호의 겹 수를 level이라고 표현하겠다.

예를 들어 level 3(세 겹의 괄호 안에 있는)인 숫자의 개수가 4개면, len[3] = 4가 된다.

 

여기서 주의해야할 점은 괄호 직전의 숫자 K는 괄호 안의 숫자 길이에 K배를 하는 용도이므로 숫자의 개수에 포함하지 않았다.

 

가장 앞쪽부터 시작해 현재 보고 있는 숫자가 몇 겹의 괄호 안에 있는지 파악해주었다.

 

숫자가 나오면 현재 괄호 내의 숫자의 개수를 세고, '('가 나오면 len의 index를 1 증가시켜주었고 ')'가 나오면 len의 index를 1 감소시켰다.

이 방법으로 25(432(5)24()53)처럼 괄호 안에 동일한 level의 괄호가 여러개 있는 경우도 가능하게 되었다.

 

 

코드

#include <bits/stdc++.h>
#define MAX 51
using namespace std;

char S[MAX];
int len[MAX], K[MAX];
// len: 숫자 길이 저장 배열, K: 괄호 앞 숫자
// 몇 겹의 괄호인지에 따라 index 배정
// 괄호에 포함되지 않은 가장 바깥 숫자면 index = 0, 한 겹의 괄호 안에 있는 수는 index = 1, ...  

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> S;
	int i, cur = 0, num = 0, size = strlen(S);
	for (i = 0; i < size; i++) {
		if (S[i] == '(') {
			len[cur]--;	// 괄호 앞의 K는 길이에 포함시키지 않으므로
			cur++;
			K[cur] = num;	// 아래 else 문에서 저장한 숫자를 괄호 앞 숫자로 확정
		}
		else if (S[i] == ')') {
			int temp = len[cur] * K[cur];
			len[cur] = 0;	// 해당 괄호는 끝났으므로 0으로 초기화
			cur--;
			len[cur] += temp;
		}
		else {
			len[cur]++;
			num = S[i] - '0';	// 괄호 앞 숫자일 수 있으므로 일단 저장
		}
	}
	cout << len[0];
}

 

성능

코드 제출 결과