백준 압축(1662)

압축

1. 힌트

1) 일반적인 수식 계산 순서와 같이 괄호 안에 있는 것을 먼저 계산해야합니다.

2) 스택을 이용하면 괄호 안의 계산을 먼저 할 수 있습니다.

3) 문제에서 요구하는 것은 압축되지 않은 문자열의 길이이므로 괄호에 붙어있지 않은 숫자들은 모두 $1$로 바꾸어도 상관이 없습니다.

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

언뜻 보면 우선 순위를 지켜서 수식을 계산하는 문제처럼 보입니다. 괄호가 있으므로 우선 순위를 지켜서 스택을 이용하면 계산하는 과정을 구현할 수 있겠죠.

$K(Q)$와 같은 연산은 괄호 안의 문자열의 길이가 얼마가 되는지 계산한 뒤 처리되어야합니다. 그렇다면 스택에 넣는 원소는 문자열의 길이 혹은 여는 괄호, 닫는 괄호만 넣읍시다. 만약 문자열의 길이가 아니라 문자열 자체를 넣어버리면 다음과 같은 문제가 발생합니다.
$1(42(3))$
$4$는 거기 있는 문자가 $4$일 뿐이지 문자열의 길이가 $4$라는 의미가 아닙니다. 반면에 $2(3)$을 계산해서 나온 문자열의 길이 $6$은 실제로는 $6$이라는 문자열이 있는 것이 아니죠.

2) 문제를 단순화할 수 없을까?

그러므로 괄호에 붙어있지 않은 숫자의 길이는 $1$이므로 모두 $1$로 바꿔주면 더 간편하게 계산 할 수 있습니다. 다음과 같은 규칙으로 문자를 넣도록 하죠.
1. 우선 괄호에 붙어있지 않은 숫자는 모두 $1$로 바꿉니다
$33(562(71(9))) \to13(112(11(9)))$
2. 문자열을 차례로 순회하면서 닫는 괄호가 아니라면 무조건 스택에 집어넣습니다.
3. 닫는 괄호라면 여는 괄호가 나올 때 까지 스택의 값을 모두 더한 뒤에 여는 괄호 왼쪽에 있는 수와 곱한 값을 스택에 다시 넣습니다.
4. 위 과정이 끝나면 스택에 남은 값을 모두 더합니다.

1번 과정이 귀찮아서 저는 구현할 때 넣어줄때마다 확인하는 식으로 구현했는데 1번 과정으로 전처리 하는 것이 더욱 간단해 보입니다.

3. 구현

제일 처음에 나온 조건문이 매우 복잡합니다 위에 나와있는 규칙 1번을 구현한 조건문입니다... 그리고 자바는 stack에 여러가지 자료형을 넣기가 복잡해서 상당히 괴악하게 구현되었습니다 (-1이 여는 괄호라던가)

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] S = br.readLine().toCharArray();
		Stack<Integer> st = new Stack<>();
		for (int i = 0; i < S.length; i++) {
			// S[i]가 숫자고 S[i + 1]이 숫자거나 닫는 괄호거나
			// S[i]가 마지막에 있는 숫자인 경우 1로 바꾼다
			if ('0' <= S[i] && S[i] <= '9' && 
			((i + 1 < S.length && (('0' <= S[i + 1] && S[i + 1] <= '9') || 
			S[i + 1] == ')')) || 
			i == S.length - 1)) {
				S[i] = '1';
			}
			if (S[i] == ')') {
				int sum = 0;
				while (st.peek() != -1) sum += st.pop();
				st.pop();
				st.push(st.pop() * sum);
			} else {
				st.push(S[i] == '(' ? -1 : S[i] - '0');
			}
		}
		int sum = 0;
		for (int x : st) sum += x;
		System.out.println(sum);
	}

}

1) 시간 복잡도

Stack의 pop연산과 push연산은 $O(1)$입니다. 문자열 원소들은 한 번씩만 확인하므로 $O(len(S))$입니다. 마지막에 스택에 남은 원소들을 순회할 때도 어차피 스택에는 문자열의 길이보다 더 많은 값이 들어가 있을 수 없기 때문에 마찬가지로 $O(len(S)$입니다.

2) 테스트 케이스

practice1님의 반례 모음