[Day3] 문자열 압축 해제

💡문제

• 시간 제한: 1초

엘리스 토끼는 문자열을 직접 압축 해제하려고 합니다.

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열 중 어떤 부분 문자열은 K(Q)와 같이 압축할 수 있습니다. 이것은 Q라는 문자열이 K 번 반복된다는 뜻입니다. K는 한 자릿수의 정수이고, Q는 0자리 이상의 문자열입니다.

예를 들면, 53(8)은 다음과 같이 압축을 해제할 수 있습니다.

53(8) = 5 + 3(8) = 5 + 888 = 5888

압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하세요.

지시사항

입력

• 첫째 줄에 압축된 문자열 S를 입력합니다.
• S의 길이는 최대 50입니다.
• 문자열은 (, ), 숫자로만 구성되어 있습니다.

출력

• 압축되지 않은 문자열의 길이를 출력합니다.

입력 예시

11(18(72(7)))

출력 예시

26

 

---

💡알고리즘 설계

• 데이터 구조:
  • Stack<Character> stack: 문자열을 처리하기 위한 스택.
  • int[] depthResult: 각 깊이(괄호 중첩 수준)에서의 결과를 저장하는 배열.
  • int depth: 현재 괄호의 깊이를 추적함.
• 문자열 처리:
  • 문자열의 각 문자를 순회하며 처리함.
  • ')'가 아닌 문자는 모두 스택에 푸시함.
  • '('를 만나면 깊이를 증가시키고, 해당 깊이의 결과를 0으로 초기화함.
• ')' 문자 처리:
  • 스택을 역순으로 탐색하여 대응하는 '('를 찾음.
  • 괄호 안의 문자 수를 계산함.
  • 괄호 앞의 숫자를 가져와 반복 횟수로 사용함.
  • 계산된 길이를 이전 깊이의 결과에 더함.
  • 처리가 끝난 문자들을 스택에서 제거함.
• 결과 계산:
  • depthResult[0]는 모든 괄호 처리가 끝난 후의 길이.
  • stack.size()는 괄호 밖에 남아있는 문자의 수.
  • 이 둘을 더해 최종 길이를 계산함.

 

💡코드

import java.util.Stack;

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

        Stack<Character> stack = new Stack<>();
        int[] depthResult = new int[50];
        int depth = 0;

        for(char c : str.toCharArray()) {
            if(c != ')') {
                if(c == '(') {
                    depth++;
                    depthResult[depth] = 0;
                }
                stack.push(c);
            } else { // c == ')'
                // 스택을 역순으로 대응하는 '('를 찾음
                for(int i=stack.size()-1; i>=0; i--) {
                    if(stack.get(i) == '(') {
                        int num = depthResult[depth];
                        for(int j=i+1; j<stack.size(); j++) {
                            num++;
                        }
                        depthResult[--depth] += num * Character.getNumericValue(stack.get(i-1));
                        while(stack.size() >= i) {
                            stack.pop();
                        }
                        break;
                    }
                }
            }
        }
        System.out.println(depthResult[0] + stack.size());
    }
}

 

💡시간복잡도

O(n)

 

💡 틀린 이유

기존 코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String answer_s = "";
    Stack<String> stack = new Stack<>();
    String str = br.readLine();
    for(int i=0; i<str.length(); i++) {
        char c = str.charAt(i);
        if(c == ')') break;
        stack.push(String.valueOf(c));
    }

    while(!stack.isEmpty()) {
        String s_pop = stack.pop();
        if(s_pop.equals("(")) {
            int k = Integer.parseInt(stack.pop());
            answer_s = stack.pop() + answer_s.repeat(k);
        } else {
            answer_s = s_pop + answer_s;
        }
    }

    System.out.println(answer_s.length());
    br.close(); bw.close();
}

• 괄호 처리의 제한:
  • 코드가 첫 번째 ')'를 만나면 입력 처리를 중단함. 이로 인해 중첩된 괄호나 여러 개의 괄호를 포함하는 입력을 제대로 처리하지 못함.
• 깊이(depth) 처리 없음:
  • 중첩된 괄호 구조를 처리할 수 있는 매커니즘이 없음.
• 한 자리의 숫자만 처리할 수 있음.
• 코드가 스택을 한 번만 순회해서, 중첩 구조를 해석하지 못함.

11(18(72(7))) 예시의 경우만 생각하여 중첩 구조를 생각하지 못했다.

 

정리

• 모든 문자를 처리한다.
• 문자열을 직접 만들지 않고 길이만 계산한다.
• 깊이(depth)를 사용해 중첩 구조를 처리한다.
• 여러 자리 숫자를 처리할 수 있다.
• 복잡한 중첩 구조를 해석할 수 있다.

 

💡 다른 풀이

깊이를 카운트 하지 않고, 길이만 더하는 방법

import java.io.*;
import java.util.*;

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

        Stack<Character> stack = new Stack<>();
        int depth = 0;
        int[] depthResult = new int[50];
        int s_length = 0;

        for(char c : str.toCharArray()) {
            if(c != ')') {
                if(c == '(') {
                    depth++;
                    depthResult[depth] = 0;
                }
                stack.push(c);
            } else { // c == ')'
                for(int i=stack.size()-1; i>=0; i--) {
                    if(stack.get(i) == '(') {
                        int num = s_length;
                        for(int j=stack.size()-1; j>i; j--) {
                            num++;
                        }
                        s_length = num * Character.getNumericValue(stack.get(i-1));
                        while(stack.size() >= i) {
                            stack.pop();
                        }
                        break;
                    }
                }
            }
        }

        s_length = s_length + stack.size();
        System.out.println(s_length);
    }
}

 

depth를 사용하지 않아도 위처럼 간단하게 작성할 수 있다.

 

💡 느낀점 or 기억할정보

알고리즘 설계를 할 때 입력의 모든 가능한 경우를 고려해야 한다는 것을 느꼈다.

`Character.getNumericValue()` : 숫자 형태의 char 형을 int 형으로 변환하는 메서드이다.