[알고리즘 / 백준] 1662 - 압축

www.acmicpc.net/problem/1662

1662번: 압축

문제는 위에서 확인할 수 있으며 예제로 주어진 압축 문자의 압축을 푸는 방법을 보면 아래와 같습니다.

 

33(562(71(9)))

=> 33(562(79))

=> 33(567979)

=> 3567979567979567979

=> 결과: 19

 

처음에는 아주 쉽게 생각해서 순서대로 스택에 저장하다가 ")" 가 들어온 경우 "(" 를 찾을 때까지 앞으로 이동하면서 그 수를 세고 "(" 를 만나면 그 앞에 있는 수를 곱해서 다시 카운트에 넣는 방법을 사용하였습니다. 하지만 이 경우는 완벽하게 ((())) 형태로 있을 때만 가능한 경우이고 33(562(71(9)))44(2) 와 같이 ((()))() 식의 괄호가 들어오면 처리하지 못하는 문제가 있었습니다.

 

따라서 입력 값이 "(" 인 경우는 그냥 그대로 스택에 저장하고, ")" 인 경우는 앞으로 이동하면서 "(" 를 찾을 때까지 사이의 수(사이 문자열의 길이)를 더하고 "(" 괄호를 찾으면 그 앞에 있는 수와 사이의 수를 곱해서 다시 스택에 저장하였습니다.

그리고 문자가 들어오는 경우를 "숫자, (" 와 "숫자, 숫자" 인 경우로 나누어 "숫자, (" 인 경우는 해당 숫자가 반복 횟수이기 때문에 그대로 스택에 저장하고, "숫자, 숫자" 인 경우는 단순 문자열이기 때문에 문자열의 길이인 1을 저장하는 방식으로 문제를 해결하였습니다.

 

결과적으로 스택에 저장되는 순서대로 위 예제를 살펴보면 다음과 같습니다.

입력: 33(562(71(9)))

1 3 ( 1 1 2 ( 1 1 ( 1 => ) 가 들어오면 1 * 1

=> 1 3 ( 1 1 2 ( 1 1 => ) 가 들어오면 2 * (1 + 1)

=> 1 3 ( 1 1 4 => ) 가 들어오면 3 * (1 + 1 + 4) 

=>1 18

=> 결과: 1 + 18 = 19

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

s = stdin.readline().strip()
stack = list()

for i in range(len(s)):
    if s[i] == "(":
        stack.append("(")
    elif s[i] == ")":  # 닫는 괄호가 들어오면
        cnt = 0
        while True:
            tmp = stack.pop()  # 다시 앞으로 돌아가면서
            if tmp == "(":     # 여는 괄호를 만날 때까지 반복
                break
            cnt += tmp         # () 사이에 저장된 문자열의 수를 더하기
        stack.append(int(stack.pop()) * cnt)  # "( 앞에 있는 반복 횟수 * () 사이 문자열의 크기" 를 구해서 다시 저장하기
    elif i < len(s) - 1 and s[i + 1] == "(":  # 숫자, ( 조합이 들어온 경우
        stack.append(int(s[i]))  # 숫자 그대로 반복 숫자로 추가
    else:  # 숫자, 숫자 조합이 들어온 경우
        stack.append(1)  # 숫자의 크기는 문자열 1개이므로 1을 저장

# 총 문자열의 길이 구하기
answer = 0
for st in stack:
    answer += st
print(answer)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] strings = br.readLine().split("");
        List<Integer> stack = new ArrayList<>();

        for (int i = 0; i < strings.length; i++) {
            if (strings[i].equals("(")) {
                stack.add(-1);
            } else if (strings[i].equals(")")) {
                int cnt = 0;
                while (true) {
                    int tmp = stack.remove(stack.size() - 1);
                    if (tmp == -1) {
                        break;
                    }
                    cnt += tmp;
                }
                stack.add(stack.remove(stack.size() - 1) * cnt);
            } else if (i < strings.length - 1 && strings[i + 1].equals("(")) {
                stack.add(Integer.parseInt(strings[i]));
            } else {
                stack.add(1);
            }
        }

        int answer = 0;
        for (int s: stack) {
            answer += s;
        }

        System.out.println(answer);
    }
}