[백준 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));
    }
}