문제

문제링크

풀이

접근 방법

사실 괄호만 봐도 스택 문제같은 느낌이 옵니다. 하지만 저는 문자열로 풀었습니다. 스택과 원리는 같을 것 같아 작성해봅니다.

핵심 원리

핵심 원리는 다음과 같습니다.

레이저가 나온다면 이전에 나왔었던 '('의 갯수만큼 정답에 더한다.

파란색 부분을 보고 힌트를 얻을 수 있습니다.
레이저가 나온다면 여태까지 나왔던 다리의 갯수만큼 정답이 늘어납니다. 즉 이전에 쌍으로 닫히지 않았던 '('의 갯수만큼 더해줍니다.

그림으로 차근차근 설명하기 전에, 제가 푼 방식은 다음과 같습니다.
1. counter와 answer를 0으로 초기화한다.
2. '('가 나오면 counter를 1 증가시킨다.
3. 카운터와 정답 변수를 0으로 초기화한다.
4. ')'가 나오면 카운터를 1 감소시킨다.
4-1. 만약 이전 코드가 ')'이면 레이저이므로 여태까지의 counter를 answer에 더합니다.
4-2 그게 아니라면 다리의 끝이므로 여태까지의 answer에 1을 더합니다.

과정

초기 상태 입니다.

'('이므로, 카운터를 1 증가해줍니다.

')'이므로, 카운터를 1 감소시킵니다. 이전이 '('이므로 레이저지만, 카운터 0을 정답에 더해도 0 입니다.

레이저 ')'이전까지 왔습니다.

')'이므로 카운터를 1 감소시키고, 이전이 '('이므로 카운터를 정답에 더해줍니다.

이전과 마찬가지로 카운터를 1 감소시키고 더해줍니다.

')'이므로 카운터를 1 감소시키고, 이전이 '('가 아니므로, 다리의 끝 입니다. 정답에 1을 더해줍니다.

이 과정을 반복하면 정답이 17이 나옵니다.

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<>();
        int count = 0;
        int answer = 0;
        String str = br.readLine();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            // '('면 카운터 증가
            if (c == '(') {
                count++;
            }
            // ')'
            else if (c == ')') {
                count--;
                // 전 단어가 '('면 레이저
                if (i > 0 && str.charAt(i - 1) == '(') {
                    answer += count;
                }
                // 전 단어가 '('가 아니라면 막대의 끝 -> +1을 해준다.
                else {
                    answer++;
                }
            }
        }
        System.out.println(answer);
    }
}