백준 알고리즘 문제 중에서 해결하면서 힌트를 참고했거나, 어려웠던 문제들에 대한 정리입니다

문제번호	제목	난이도
1662	압축	골드 5

1662번 압축

해결 코드

import java.io.*;
import java.util.*;


/**
 * 풀이 과정:
 * - 고민과 풀이:
 *
 * 재귀
 * 1. 함수 형태 compress(주어진 문자열, 현재 위치, 탐색 문자열, 개수)
 * 2. base Condition 현재 문자열이 ')'이면 종료
 * 3. 재귀식 if(주어진문자열.charAt(현재위치) == '(') -> compress(주어진 문자열, 현재 위치+1, ')', 개수+1)
 *
 * - 문제 해결:
 * 1. 스택과 재귀를 같이 활용하는 문제이다
 * 2. 먼저 (와 )의 위치를 저장해놔야한다. 이때 스택과 배열을 사용한다
 * 3. 이후 함수를 사용해서 순회하는데, 만약 (가 발견되면 2번에서 지정한 범위만큼 진행되도록 재귀함수를 실행한다
 * 재귀
 * 1. 함수 형태 compress(시작위치, 끝나는 위치)
 * 2. base condition 자동 종료
 * 3. 재귀식 compress(i+1, friend[i])
 *
 * 시간복잡도: O()
 * 공간복잡도: O()
 *
 */


public class Main {

    static int count = 0;
    static int[] pos;
    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 s = br.readLine();
        Stack<Integer> stack = new Stack<>();
        pos = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '('){
                stack.add(i);
            }
            if(s.charAt(i) == ')'){
                pos[stack.pop()] = i;
            }
        }

        count = compress(s, 0, s.length());

        bw.write(count+"");
        br.close();
        bw.close();
    }

    private static int compress(String s, int start, int end) {
        int tmp = 0;
        for (int i = start; i < end; i++) {
            if(s.charAt(i) == '('){
                tmp += Integer.parseInt(String.valueOf(s.charAt(i-1))) * compress(s, i+1, pos[i])-1;
                i = pos[i];
            }else{
                tmp++;
            }
        }
        return tmp;
    }
}

해결방법:

1. 스택과 재귀를 같이 활용하는 문제였다 어떤 문제든지 여러 알고리즘을 같이 사용해서 해결해야할 수도 있음을 꼭 명심하자
2. 이 문제는 따로 base Condition을 지정할 수 없었다. 스택에서 (와 )의 범위를 지정해서 배열에 저장해놨고 이것을 활용해서 순회하고 종료하기 떄문이다
3. 스택에는 (를 찾으면 그 위치를 넣고 )가 나오면 스택의 pop의 위치에 )의 위치를 넣어준다
4. 재귀 함수에서는 시작과 종료의 범위를 파라미터로 받는다
5. 순회하는 동안 만약 (가 나오면 문제에서 주어진 방법대로 진행한다
6. 먼저 이전 값을 Integer형으로 파싱해주고 이후 나오는 값과 곱해준다
7. 그다음 재귀함수를 통해 (의 다음값부터 저장된 배열을 통해 )의 위치까지 순회하도록 한다.
8. 이어서 (의 위치도 count되기 때문에 1을 빼준다
9. 만약 (가 아닌 경우는 그냥 일반 숫자이므로 개수를 증가시킨다
10. 순회가 종료된 뒤에는 지금까지 세어진 수를 리턴해서 출력하면 정답이 된다.