[알고리즘 문제풀이] 백준 1662 압축 ( 도와주세요 🙏🏻 )

문제 링크 - 백준 1662 압축

이 문제는 실은 며칠전에 푼 문젠데 찜찜했던 부분이 있어서 다시 풀었다.

도와주세요 🙏🏻 궁금한 부분 !

그리고 다시 풀면서 정규식으로 하면 문자열이 너무 길어져서 시간 초과가 나겠지 하면서도 한 번 테스트를 해보고 싶어서 풀어보았는데 채점 1%에서 실패가 떴다.. 질문에 올라온 반례들을 다 실행시켜봐도 문제가 없었는데.. 그리고 시간이 오래 걸려서 문제지 가장 압축을 실제로 푸는 방법이라 반례가 문제인 거 같지는 않은데 뭐가 문제일까 궁금하다..

정규식 풀이 코드도 아래 첨부할테니 문제를 알겠는 분들은 답변 남겨주시면 감사할 거 같습니다.

문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

입력

첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다.

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 int범위다.

예제

입력 1

33(562(71(9)))

출력 1

19

풀이 방법

괄호 안에 있는 문자열을 괄호 앞의 숫자만큼 반복해야 하는 것이기 때문에 먼저 괄호 안에 있는 문자열을 찾아내야한다 ! 그렇기 때문에 괄호 쌍을 찾아주기 위해서 Stack을 사용하여 문제를 풀어보았다.

문자열을 반복하며 현재 문자를 스택에 넣어주었다. 이 때, 현재 문자가 ')' 닫는 괄호인 경우에는 '(' 여는 괄호가 나올 때까지 스택을 pop 해주었다 ! 그러면서 괄호 사이의 문자가 몇 개인지 카운트 해주었다. 여는 괄호를 만나면 하나 더 pop을 하여 그 숫자와 문자열의 길이를 곱해주어 압축을 풀어준다.

이 때, 압축된 문자열의 형태가 재귀처럼 괄호 안에 또 괄호가 있을 수 있는 구조이기 때문에, 압축을 푼 문자열의 길이를 다시 스택에 넣어주었다. 단, 이것이 문자가 아닌 길이라는 것을 구분하기 위해 * 구분자를 붙여주었다.

문자열을 반복하며 압축을 모두 푼 후에는 스택을 탐색하면서 남아있는 문자나 압축이 풀린 문자열의 길이를 반영하여 최종 문자열의 길이를 구해주었다 !

코드

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

public class Main {
    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 target = br.readLine();
        Stack<String> stack = new Stack<>();
        int len;
        for(int i=0; i<target.length(); i++){
            if(target.charAt(i) == ')'){
                len = 0;
                while (!stack.peek().equals("(")){
                    if(stack.peek().charAt(0) == '*') len+=Integer.parseInt(stack.pop().substring(1));
                    else{
                        stack.pop();
                        len++;
                    }
                }
                stack.pop();
                stack.push("*" + (len*Integer.parseInt(stack.pop())));
            }else{
                stack.push(String.valueOf(target.charAt(i)));
            }
        }
        len = 0;
        while(!stack.isEmpty()){
            if(stack.peek().charAt(0) == '*') len+=Integer.parseInt(stack.pop().substring(1));
            else{
                stack.pop();
                len++;
            }
        }
        bw.write(len + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

정규식 풀이 코드

간단한 풀이를 덧붙이자면, (Q)를 찾아서 K(Q)부분 전체를 Q.repeat(K)로 replace해주는 코드이다. 즉 진짜 압축을 푼 문자열을 만들어서 길이를 출력하는 형태이다 ! 물론 괄호 안에 또 괄호가 있는 형태에도 닫는 괄호를 먼저 만나는 경우부터 수행하기 때문에 가장 안의 레벨부터 압축을 풀게 되어있어 문제가 없다 !

그치만 채점 결과 1%부터 실패가 뜬다.. 실패해도 시간초과가 맞는 것 같은데 ! 뭔가 실수를 한 것이 있는 거 같은데 모르겠다.. 아시는 분 도와주세요 🙏🏻

import java.io.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    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 target = br.readLine();
        Pattern pattern = Pattern.compile("[(][0-9]+[)]"); // 정규식 이용해서 (숫자) 형태의 패턴 찾기 
        Matcher matcher;
        while (true){
            matcher = pattern.matcher(target);
            if(!matcher.find()) break; // 더이상 위의 패턴 형태의 문자열이 없으면 종료 
            target = target.replace(target.charAt(matcher.start()-1) + matcher.group(), matcher.group().substring(1, matcher.group().length()-1).repeat(target.charAt(matcher.start()-1)-'0')); // 찾은 패턴에서 괄호를 제거한 숫자부분만 여는 괄호 앞의 숫자만큼 반복한 문자열로 replace
        }
        bw.write(target.length() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}