[BOJ] 압축 - 1662 (Java)

https://www.acmicpc.net/problem/1662

 

1662번: 압축

[풀이]

K(Q) 는 K번만큼 반복되는 Q라는 문자열을 압축해놓은 것이다.

 

예시로 

10342(76)

이런 문자열이 주어지면 

1034 2(76) => 10347676

이런식으로 압축이 풀어지고

 

압축이 해제된 문자열의 길이를 리턴해주면 된다.

 

하지만 입력값으로 9(9(9(9(9(9(123456789))))) 와 같은 괴랄한 문자열이 들어올 수 있고

 

실제 문자열자체를 구해내서 문자열의 길이를 리턴하게되면 메모리초과가 뜬다.

 

내가 생각한 방법은

• 압축을 풀어나갈 괄호의 시작위치와 끝나는 위치, '('앞에 위치한 숫자를 알아낸다.
• 압축을 풀었을 때 길이를 스택에 따로 저장해둔다.
• 괄호안에 원래존재하던 문자열이 길이와 스택에 저장해둔 문자열의 길이를 더해서 최종 리턴한다.

재귀 + 스택을 이용했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class BOJ_1662 {
    static int count;
    static Stack<Integer> stack;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        count = 0;
        stack = new Stack<>();
        for(int i=0;i<str.length();i++){
        	//재귀함수의 종료 조건으로 문자열 내에 괄호의 갯수가 0개일 때로 정했다.
            if(str.charAt(i) == '(' || str.charAt(i) == ')'){
                count++;
                continue;
            }
        }
		
        //만약 괄호가 존재하지않는 문자열이면 그 자체 길이를 바로 리턴해준다.
        if(count == 0){
            System.out.println(str.length());
            System.exit(0);
        }
        dfs(str, count);
    }
    
    //재귀함수
    public static void dfs(String str, int count){
    
    //괄호가 다 지워졌다면
        if(count == 0){
        
        	//남아있는 순수문자열의 길이와 스택에 저장된 길이를 더해준다.
            int total = 0;
            
            //ex) (9,4,) => 스택에 저장된 길이가 2개 있다는 뜻(","의 갯수만큼)
            while(!stack.isEmpty()){
                total += stack.pop();
            }
            String[] splitTmp = str.split(",");
            for(String s : splitTmp){
                if(!"".equals(s))
                    total += s.length();
            }
            System.out.println(total);
            System.exit(0);
        }else{
            for(int i=0;i<str.length();i++){

                //'(' 괄호 위치(제일 뒤쪽에 있는 괄호부터 찾음)
                int startIndex = str.lastIndexOf("(");

                //괄호안의 문자열이 몇 번 반복되는지
                char num = str.charAt(startIndex-1);

                //')' 괄호 위치
                int endIndex = 0;
				
                // '('괄호를 찾았다면 그 위치에서부터 제일 가까운 ')'괄호를 찾는다.
                for(int j=startIndex;j<str.length();j++){
                    if(str.charAt(j) == ')'){
                        endIndex = j;
                        break;
                    }
                }

                //괄호안에 문자열 ex) 2(123) -> tmpDelete : 123
                String tmpDelete = str.substring(startIndex+1, endIndex);

                //앞에 숫자랑 괄호 포함한 문자열
                String deleteStr = str.substring(startIndex-1, endIndex+1);
                
                //만약 1() 과 같이 계산할 길이가 없으면 
                //그대로 공백으로 바꿔주고 재귀실행
                if("".equals(tmpDelete)){
                    str = str.replace(deleteStr, "");
                    dfs(str, calc(str));
                }
                
                int unzipLength = -1;
                if(tmpDelete.contains(",")){
           //ea 변수를 사용한 이유는 따로 적음..
                    int pureStrLength = 0;
                    int calcedLength = 0;
                    int ea = 0;
                    for(int j=0;j<tmpDelete.length();j++){
                        if(tmpDelete.charAt(j) == ',') ea++;
                    }
                    String[] splitTmp = tmpDelete.split(",");
                    for(String s : splitTmp){
                        if(!"".equals(s)){
                            pureStrLength += s.length();
                        }
                    }
                    while(ea-->0){
                        calcedLength += stack.pop();
                    }
                    int totalLength = pureStrLength + calcedLength;
                    unzipLength = totalLength * (num-'0');
                    stack.push(unzipLength);
                }else{

                    //괄호 안에 숫자만 있는 경우
                    //길이를 계산해서 스택에 넣어준다.
                    unzipLength = unzip(tmpDelete, num-'0');
                    stack.push(unzipLength);

                }
                
                //정확한 구간에 replace를 하기 위해 StringBuilder사용
                //예를들어 지워야할 문자열이 2(2) 인데 문자열 전체가 2(2(2(2)2(2))) 이런식이면
                //지워야되는 2(2)말고도 지워져서 사용함
                StringBuilder sb = new StringBuilder();
                sb.append(str);
                
                //압축이 풀린 부분은 ","로 바꿔줌 
                //ex) 12(34(56)) => 12(3,)) 가 되는데 실제로는 12(3(56565656)) 이다.
                //압축이 풀린 문자열의 길이(unzipLength = 8)는 스택에 저장된다.
                str = String.valueOf(sb.replace(startIndex-1,endIndex+1, ","));
				
                //재귀 반복
                dfs(str, calc(str));
            }
        }
    }
	
    //압축을 풀고 길이를 리턴해주는 함수
    public static int unzip(String str, int num){
        return str.length() * num;
    }
	
    //재귀를 돌릴때마다 괄호의 갯수를 반복해서 체크하고 리턴해주는 함수
    public static int calc(String str){
        int count = 0;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i) == '(' || str.charAt(i) == ')')
                count++;
        }

        return count;
    }
}

ea라는 변수를 사용한 이유는

 

테스트케이스 중에 괄호 안에 괄호가 아니라 괄호가 따로따로 있는 경우 때문이다.

 

예를 들어

12(34(56))23(2)

라는 문자열이 있다면 로직에 따라서 제일 뒤쪽의 괄호부터 풀게된다.

12(34(56))23(2) => 12(34(56))2,

unzipLength : 3

Stack : 3

하지만 괄호를 모두 풀때까지 다른 괄호를 다시 찾아서 압축을 풀기때문에

 

결국 마지막에 풀리는 괄호부터 스택에 저장된 길이값을 이용해야 한다.

 

그다음 압축을 풀어보면

 

12(34(56))2, => 12(3,)2,

unzipLength : 8

Stack : 3, 8

이렇게 되는데 만약 남아있는 괄호안에

 

순수문자열인 "3"과 스택에 저장된 값을 이용하려면

 

가장 최근에 저장된 값을 사용해야되고

 

후입선출인 스택이 딱이다.

 

근데 여기서 스택이 빌때까지 pop을 하는게아니라

 

압축이 풀려 ","로 변환된 길이가 몇개인지 체크해서

 

그 갯수만큼만 pop하게한뒤

 

길이를 계산해주면된다