[BOJ-1662] 압축

백준 2806 DNA 발견

 

1662번: 압축

 

문제 설명

 

 - 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축할 수 있다.

 

 - K는 한 자리 정수이고, Q는 0자리 이상의 문자열이다.

 

 - 이 Q라는 문자열이 K번 반복된다는 뜻이다.

 

 - 압축된 문자열이 주어졌을 때 이 문자열의 원래 문자열의 길이를 구하라.

---

 

입력 값

 

 - 첫째 줄에 압축된 문자열 S가 들어온다.

 

 - S의 길이는 최대 50이다.

 

 - 문자열은 (, ), 0-9 사이의 숫자로만 들어온다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 압축된 문자열을 바탕으로 원래 문자열의 길이를 찾는 것이다.

 

 - 즉, 어떠한 문자열인지를 찾기 보다는 길이만 찾으면 된다는 것이다.

 

 - 압축된 문자열은 K(Q) 형태가 되기 떄문에 괄호가 닫히는 순간 괄호 안에 있는 문자열을

   K번 반복하는 방법으로 문자열을 원복시키면 된다.

 

 

---

 

 

소스 코드

 

package boj;

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

//https://www.acmicpc.net/problem/1662
public class boj_0816_1662 {
    public static void main(String[] args) throws IOException {


        System.setIn(new FileInputStream("input.txt"));

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String s = bf.readLine();

        int result=0;

        Stack<RealNumber> stack = new Stack<>();

        for(int i=0;i<s.length();i++){
            char nowChar = s.charAt(i);

            if(nowChar==')'){
                int sum=0;
                while(!stack.empty()){
                    RealNumber stackNum = stack.peek();
                    stack.pop();

                    if(stackNum.num==-1){
                        stackNum=stack.peek();
                        stack.pop();

                        stack.push(new RealNumber(stackNum.num*sum,true));
                        break;
                    }
                    else{
                        sum+= stackNum.getNum();
                    }
                }
            }
            else if(nowChar=='('){
                stack.push(new RealNumber(-1));
            }
            else{
                stack.push(new RealNumber(nowChar-'0'));
            }

        }

        while(!stack.empty()){
            RealNumber stackNum = stack.peek();
            stack.pop();

            result+=stackNum.getNum();
        }

        System.out.println(result);

    }

    static class RealNumber{
        int num;
        boolean isReal;

        public RealNumber(int num) {
            this.num = num;
            isReal=false;
        }

        public RealNumber(int num, boolean isReal) {
            this.num = num;
            this.isReal = isReal;
        }

        public int getNum(){
            if(isReal){
                return this.num;
            }
            return 1;
        }
    }
}