[알고리즘 PS] 백준 10799번 쇠막대기 자바 문제 풀이

문제

해당 포스팅은 백준의 10799번 쇠막대기 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

이번 문제는 스택을 이용해서 문제를 접근해야 한다.

 

우선 쇠막대기가 잘리기 위해서는 () 괄호가 등장해야 한다.

괄호가 등장하면 즉, 레이저가 등장하면 지금까지 누적되어 있던 쇠막대기 (가 잘리게 된다.

 

우리는 이 것을 보고 stack.size()만큼 추가해주면 된다는 것을 알 수 있다.

 

여기서 등장할 수 있는 기호는 2가지이므로 2개로 나눠보자.

1. ( 가 등장한 경우
2. ) 가 등장한 경우

( 가 등장한 경우

( 가 등장한 경우는 쇠막대기를 절단기 아래에 놓는 부분이라고 생각하면 된다.

즉, stack에 push 해주면 된다.

) 가 등장한 경우

) 가 등장한 경우는 또 2가지로 나뉜다.

1. 레이저가 나올 경우
2. 쇠막대기가 끝나는 경우

레이저가 나올 경우

레이저가 나올 경우는 바로 직전 요소가 (인 경우에 해당한다.

레이저가 나온 경우에는 쇠막대기들의 갯수만큼 즉 stack.size()만큼 정답 값에 누적해주면 된다.

 

쇠막대기가 끝나는 경우
쇠막대기가 끝나는 경우는 조금 생각해봐야 한다.

쇠막대기가 끝났다는 경우에는

---- 쇠막대기

위와 같은 쇠막대기가 있다고 가정해보자.

 

그럼 이 쇠막대기가 잘리면 몇개의 쇠막대기가 나올까?

 

-- | -- 쇠막대기

2개의 쇠막대기가 나온다.

 

그럼 3개의 쇠막대기가 있는 경우 가장 짧은 쇠막대기를 잘라보자.

 

--|-- // <-- 무조건 하나가 남음
--|------ // <-- 이 쇠막대기가 끝나는 경우에도 이 쇠막대기는 하나가 더 남음
--|---------- // <-- 역시 동일

짤린 쇠막대기의 제일 상단 부분은 무조건 하나가 남게 된다.

그래서 결국 우리가 지정한 정답 값에는 +1을 해주면 되는 것이다.

 

정답 코드

public class Main {
    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[] n = br.readLine().split("");

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

        int answer = 0;
        for (int i = 0; i < n.length; i++) {
            String now = n[i];

            if(now.equals("(")) stack.push(now);
            else {
                if(n[i-1].equals("(")) {
                    stack.pop();
                    answer += stack.size();
                }else {
                    answer++;
                    stack.pop();
                }
            }
        }
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.