[백준 1662번] 압축

문제 링크: 1662번 압축

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

 

s[i]는 s[i+1]이 '('가 아닌 다른 문자이면 일반 문자열이므로 length에 1을 더해준다. s[i+1]이 '('이면 괄호 안에 오는 문자열이 반복되는 횟수를 나타내므로, 이는 괄호 안의 문자열의 길이와 곱해져야 한다. 괄호 안의 문자열에 대해서 unzip()을 호출해주고, 다음으로 처리해야 할 문자의 인덱스, 즉 i를 괄호 다음으로 넘겨서 계속 읽어나간다. 이렇게 하면 여러 개의 괄호가 있는 경우, 그리고 괄호 뒤에 또 다른 문자열이 나오는 경우도 처리할 수 있다.

오히려 문제는 '괄호 안의 문자열'이 어디부터 어디까지를 말하는 것인가에 있었다. 스택이 빌 때까지 오른쪽 괄호를 찾아 나서면, 스택이 비게 되는 지점이 왼쪽 괄호와 쌍이 맞는 괄호가 있는 지점이다. 다만 이렇게 하면 안쪽 괄호에 대해서는 또다시 동일한 과정을 수행하므로 O(N^2)이 될 것인데, 한 번에 모든 괄호의 쌍을 찾을 방법은 없을지 고민해봐야겠다.

 

Python

def unzip(s):
​​​​if len(s) == 0: return 0

​​​​length = 0
​​​​stack = 0

​​​​i = 0 # s에서 현재 인덱스
​​​​while i < len(s) - 1:
​​​​​​​​### 다음 문자가 '('가 아닌 다른 문자가 온다면 s[i]는 일반 문자이다.
​​​​​​​​if s[i+1] != '(':
​​​​​​​​​​​​length += 1
​​​​​​​​​​​​i += 1
​​​​​​​​​​​​continue

​​​​​​​​### 다음 문자가 '('가 온다면 s[i]는 반복 횟수이다.
​​​​​​​​coef = int(s[i]) # 반복 횟수

​​​​​​​​stack += 1
​​​​​​​​idx = i+1 # 왼쪽 괄호 다음 인덱스부터 시작해서 stack이 빌 때까지 오른쪽 괄호를 찾는다.
​​​​​​​​while stack > 0:
​​​​​​​​​​​​idx += 1
​​​​​​​​​​​​if s[idx] == '(': stack += 1
​​​​​​​​​​​​if s[idx] == ')': stack -= 1
​​​​​​​​# while문을 벗어나면 idx는 닫는 괄호를 가리킨다.

​​​​​​​​midLength = unzip(s[i+2:idx]) # 괄호 안의 문자열에 대해 unzip()을 호출한다.
​​​​​​​​length += coef*midLength

​​​​​​​​i = idx + 1 # 괄호 다음으로 건너뛴다.

​​​​if s[-1] != ')': length+=1

​​​​return length

s = input()
print(unzip(s))

 

Java

import java.util.Scanner;

public class Main {
​​​​static int unzip(String s) {
​​​​​​​​if (s.length() == 0) return 0;

​​​​​​​​int length = 0;
​​​​​​​​int paren = 0;

​​​​​​​​int i = 0;
​​​​​​​​while (i < s.length() - 1) {
​​​​​​​​​​​​if (s.charAt(i+1) != '(') {
​​​​​​​​​​​​​​​​length++;
​​​​​​​​​​​​​​​​i++;
​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​}

​​​​​​​​​​​​int coef = (int)(s.charAt(i) - '0');

​​​​​​​​​​​​paren++;
​​​​​​​​​​​​int idx = i+1;
​​​​​​​​​​​​while (paren > 0) {
​​​​​​​​​​​​​​​​idx++;
​​​​​​​​​​​​​​​​if (s.charAt(idx) == '(') paren++;
​​​​​​​​​​​​​​​​if (s.charAt(idx) == ')') paren--;
​​​​​​​​​​​​}

​​​​​​​​​​​​int midLength = unzip(s.substring(i+2, idx));
​​​​​​​​​​​​length += coef * midLength;

​​​​​​​​​​​​i = idx + 1;
​​​​​​​​}

​​​​​​​​if (s.charAt(s.length() - 1) != ')') length++;

​​​​​​​​return length;
​​​​}

​​​​public static void main(String[] args) {
​​​​​​​​Scanner sc = new Scanner(System.in);
​​​​​​​​String s = sc.next();
​​​​​​​​sc.close();
​​​​​​​​System.out.println(unzip(s));
​​​​}
}