백준 10799 쇠막대기 (JAVA)

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

문제 설명

괄호가 예제 처럼 주어질 때, () 이렇게 바로 열고 닫힌 것은 레이저 ( .... ) 인 괄호는 막대기 입니다.

이 레이저가 막대기를 총 몇번 부스는지 찾아내는 프로그램을 구현하면 됩니다.

 

문제에 대한 아이디어

제일 처음 생각한 아이디어는 레이저를 만나면 레이저를 ArrayList에 저장을 합니다. Stack에는 괄호를 '(' 집어넣고 ')' 이것을 만났을 때  레이저인지 판별해주고 레이저가 아니면 레이저를 저장했더 ArrayList를 돌면서 그 사이에 레이저가 몇개 있는지 검사하게 풀었습니다.

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        Deque<Integer> dq = new ArrayDeque<>();
        int answer = 0;
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i = 0; i < str.length(); ++i){
            if(str.charAt(i) == '(') dq.add(i);
            else {
                if(dq.isEmpty()) continue;
                // 레이저 담음
                if(dq.getLast() + 1 == i) {
                    arr.add(i);
                    dq.removeLast();
                }
                else {
                    int s = dq.removeLast();
                    int e = i;
                    // 괄호 사이에 레이저가 위치한지 검사
                    for(int j = 0; j < arr.size(); ++j){
                        if(s < arr.get(j) && arr.get(j) < e) ++answer;
                    }
                    answer += 1;
                }
            }
        }
        System.out.println(answer);
    }
}

하지만 레이저가 있는 것을 모두 검사하는 것은 굉장히 비효율 적이라고 생각했습니다. 

그래도 한 번 제출은 해봤지만 맞았습니다가 떴습니다. 아마도 테스트 중에 100,000개의 레이저가 있지는 않은 것 같습니다.

 

가로가 아닌 세로로 보기

좀 더 빠르게 효율적으로 풀 수 있는 방법은 무엇이 있을까? 고민을 해봤습니다.

그림을 그려놓고 보니 레이저를 처음 만들었을 때 stack에 들어있는 '(' 의 수만큼 막대기를 짤라야 한다는 것을 알았습니다. 레이저가 만들어졌을 때 스택에 남아 있는 '(' 수는 안 닫힌 막대기 이기 때문입니다. 지금 까지 가로로만 생각하고 있었는데 세로로 생각하니 문제가 아주 쉬워졌습니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        Deque<Integer> dq = new ArrayDeque<>();
        int answer = 0;

        for(int i = 0; i < str.length(); ++i){
            if(str.charAt(i) == '(') dq.add(i);
            else {
                if(dq.isEmpty()) continue;
                if(dq.getLast() + 1 == i) {
                    dq.removeLast();
                    answer += dq.size();
                }
                else {
                    answer += 1;
                    dq.removeLast();
                }
            }
        }
        System.out.println(answer);
    }
}

이렇게 푸는게 훨씬 효율적인 것 같습니다.