이 문제는 실은 며칠전에 푼 문젠데 찜찜했던 부분이 있어서 다시 풀었다.
도와주세요 🙏🏻 궁금한 부분 !
그리고 다시 풀면서 정규식으로 하면 문자열이 너무 길어져서 시간 초과가 나겠지 하면서도 한 번 테스트를 해보고 싶어서 풀어보았는데 채점 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();
}
}