[BOJ] 1662 - 압축

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1662

1662번: 압축

난이도: 골드 5

사용언어: JAVA

 

풀이

이 문제는 스택을 이용할 수도 있지만, 저는 재귀를 이용해 문제를 해결했습니다. 

 

문자열에서 '('를 만나면 재귀 함수를 시작하고 ')'를 만나면 재귀를 탈출하는 형식으로 코드를 작성했습니다. 재귀 함수의 동작은 아래와 같습니다.

 

1. '('를 만나면 재귀 함수 시작

2. 또 다른 '(' 또는 ')'를 만날 때까지 숫자들을 카운트해주면서 index를 증가 (카운트 변수 ++)

3. 또 다른 '('를 만나면 재귀 호출

4. 3에서 호출한 재귀가 완료되면 해당 재귀에서 계산한 글자의 수를 '(' 앞의 숫자와 곱하여 카운트 변수에 더해줌

5. ')'를 만나면 재귀를 탈출하면서 현재까지 카운트한 카운트 변수를 리턴

 

자세한 설명은 코드의 주석으로 대체하겠습니다. 

 

참고로 문자열로는 문자 하나하나 변환하기가 어려워서 char 배열에 문자열을 담아 사용했습니다.

 

import java.io.*;
 
class Main {
 
    static String s; // 입력받을 문자열
    static char[] arr; // 문자열을 char 배열 변환해서 사용
    static int length; // 입력받은 문자열의 길이
 
    public static int count(int index) { // index는 현재 몇 번째 문자를 처리하고 있는지에 대한 값
        int cnt = 0;
        while (index < length && arr[index] != ')') { // ')'를 만나기 전까지
            if (index + 1 < length && arr[index + 1] == '(') { // '('를 만나면
                cnt += (int) (arr[index] - '0') * count(index + 1); // 재귀 실행 후 '(' 바로 앞에 위치한 정수 값을 곱하여 cnt에 저장
                while (arr[index] != ')') // index를 ')'까지 옮겨준다.
                    index++;
                arr[index] = '#'; // 혹시 다른 재귀에서 ')'를 착각하지 않도록 한 번 체크한 ')'를 '#'으로 변경해줌
            } else if (arr[index] != '(' && arr[index] != ')' && arr[index] != '#') { // 그냥 숫자면
                cnt++; // cnt 1 증가
            }
            index++; // index 1 증가
        }
        return cnt; // cnt 리턴
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        s = br.readLine();
        arr = new char[s.length()];
        int i;
        for (i = 0; i < s.length(); i++) {
            arr[i] = s.charAt(i);
       } // char 배열에 문자열 넣어줌
        length = s.length(); // 문자열의 길이를 length에 저장 (헷갈리지 않기위해 사용)
        bw.write(String.valueOf(count(0))); // 0을 파라미터로 하는 재귀 실행
        bw.flush();
        br.close();
        bw.close();
    }
}