백준 10799 쇠막대기 Java

최백준님의 강의를 듣던 도중 접한 스택문제이다.

고민해 보지 않고 풀이법을 바로 보았던 터라 다시한번 정리하고자 한다.

 

문제내용을 정리해보면

 

어떠한 쇠막대기가 다른 쇠막대기 위에 있다면

아래에있는 쇠막대기 길이에 위에있는 쇠막대기가 포함되어야한다.

레이저로 잘린 쇠막대기의 개수를 구해라.

"( )" -> 레이저

" ( " -> 쇠막대기 시작점

" ) " -> 쇠막대기 끝점

 

분명 내가 스스로의 힘으로 풀었다면 

Stack<String>에 " ( "를 만나면 " ( "를 넣고

" ) "를 만나면 입력받은 문자열의 subString(i-1, i)로 " ( " 인지 확인하여

레이저로 취급했을 것이다.

 

아무튼 최백준님의 풀이를 보면

Stack<Integer>로 문자열에서 " ( "를 만나면 

인덱스를 스택에 넣는다.

그리고 " ) " 를 만나면 스택의 top( peek() )에 있는 변수가 지금 인덱스의 -1번째 인지

확인하고 레이저로 취급한다.

 

확실히 최백준님의 풀이가 더 간단명료하다.

 

쨋든 이 문제의 핵심은 레이저를 만났을 때 pop() 을 한번 하고

스택의 사이즈를 정답에 더해주는 것이다.

또한

ㅡ | ㅡ | ㅡ  

레이저는 두번이지만 쇠막대기는 3기이기 때문에

레이저가 아닌 " ) "에도 한덩어리씩 남는 쇠막대기가

있다고 생각하고 정답에 1을 추가한다는 것이다.

 

만약 혼자 풀었더라면 레이저 한번에 스택의 사이즈를 정답에 

더해줘야 한다는 정해진 풀이법을 몇분 만에 생각해낼 수 있었을까?

 

 

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next();
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        
        for(int i=0; i<s.length(); i++) {
            if(s.substring(i,i+1).equals("("))
                stack.push(i);
            else {
                if(stack.peek() == i-1) {
                    stack.pop();
                    count+=stack.size();
                }
                else {
                    stack.pop();
                    count++;
                }
            }
        }
        System.out.println(count);
    }