[백준 1662번][Java] 압축

www.acmicpc.net/problem/1662

1662번: 압축

 

포인트

유효한 괄호 단위로 문자열을 잘라 재귀로 넘기는게 포인트입니다.

 

여는 괄호가 나오면 이 여는 괄호의 짝인 닫는 괄호를 찾아줘야 됩니다. 그리고 그 문자열을 잘라 재귀로 넘겨주면서 글자 수를 계산하면 됩니다.

짝인 닫는 괄호를 구하는 방법은 간단합니다. 문자열을 순회하면서 openBracketCount(여는 괄호 수)를 세고 있다가 닫는 괄호가 나오면 하나씩 openBracketCount-1 해줍니다. 그러다가 openBracketCount == 0일때의 닫는 괄호가 유효한 괄호입니다.

 

 

...

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
        String s = br.readLine();
        int ret = uncompress(s);
        System.out.println(ret);
    }

    private static int uncompress(String s) {

        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char current_c = s.charAt(i);
            if(current_c >= '0' && current_c <= '9') count++;

            if(current_c == '(') {
                int closedBracketIndex = getValidClosedBracket(i,s);
                count--;
                int k = s.charAt(i-1)-48;
                count += k * uncompress(s.substring(i+1, closedBracketIndex));
                i = closedBracketIndex;
            }
        }
        return count;
    }

    private static int getValidClosedBracket(int targetOpenBracketIndex, String s) {
        int openBracketCount = 1;
        for (int i = targetOpenBracketIndex+1; i < s.length(); i++) {
            char current_c = s.charAt(i);
            if(current_c == '(') {
                openBracketCount++; continue;
            }
            if(current_c == ')'){
                openBracketCount--;
                if(openBracketCount == 0) return i;
            }
        }

        throw new RuntimeException("닫는 괄호 에러");
    }
}