[ Day 3 ] 문자열 압축 해제

 

 

 

문자열 압축 해제

• 시간 제한: 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

 

 

 

작성 코드 :

S = input()

nextdot = False
total_len = 0

for i in S[::-1]:
    if i.isalnum( ): # 숫자인경우
        if nextdot == False:
            total_len += 1
        else:
            nextdot = False
            total_len = total_len*int(i)

    elif i == "(":
        nextdot = True

print(total_len)

 

아마, 정석적인 풀이는 스택을 활용하는 것일테니 이게 정석적인 풀이는 아니라고 생각하지만,

해당 문제가 오직 길이만을 반환하면 된다는것으로 아이디어를 얻었다.

입력값이 반드시 올바른 괄호 문자열이라는 가정 하에, 해당 길이만을 지속적으로 더해가며 뒤에서 부터 앞으로 문자열을 확인하였다. 정석적인 코드는 내일 나올것이니 한번 비교해볼 예정이다.

 

 

정답 코드

C++

#include <iostream>
#include <string>
using namespace std;

string S;
int len(string str) {
  for (int i = 1; i < str.length(); i++)
    if (str[i] == '(')
      return (i - 1) +
             (str[i - 1] - '0') * len(str.substr(i + 1, str.length() - i - 2));
  return str.length();
}
int main() {
  cin >> S;
  cout << len(S);
}

Python

string = input()

stack = []
depth_result = [0] * 50
depth = 0

for ch in string:
    if ch != ")":
        if ch == "(":
            depth += 1
            depth_result[depth] = 0
        stack += [ch]
    else:
        for i in range(len(stack) - 1, -1, -1):
            if stack[i] == "(":
                num = depth_result[depth]
                for j in stack[i + 1 :]:
                    num += 1
                depth -= 1
                depth_result[depth] += num * int(stack[i - 1])
                del stack[i - 1 :]

                break
print(depth_result[0] + len(stack))

 

Java

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        String string = new java.util.Scanner(System.in).nextLine();
        
        Stack<Character> stack = new Stack<>();
        int[] depthResult = new int[50];
        int depth = 0;
        
        for (char ch : string.toCharArray()) {
            if (ch != ')') {
                if (ch == '(') {
                    depth += 1;
                    depthResult[depth] = 0;
                }
                stack.push(ch);
            } else {
                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 += 1;
                        }
                        depth -= 1;
                        depthResult[depth] += num * Character.getNumericValue(stack.get(i - 1));
                        while (stack.size() > i - 1) {
                            stack.pop();
                        }
                        break;
                    }
                }
            }
        }
        System.out.println(depthResult[0] + stack.size());
    }
}