[JAVA/10799번] 쇠막대기

문제

입력 및 출력

풀이

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

class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력받은 문자열을 하나의 문자로 분리하여 저장할 배열
        char[] pipes = br.readLine().toCharArray();

        // 후입선출의 특징을 갖는 자료구조 Stack 선언
        Stack < Character > stack = new Stack < > ();

        // 쇠막대기의 개수를 담을 변수
        int count = 0;

        // pipes배열의 길이만큼 반복문 수행
        for (int i = 0; i < pipes.length; i++) {
            // pipes[i]가 열린 괄호일 경우
            if (pipes[i] == '(') {
                stack.push(pipes[i]);
                count++;
            }
            // pipes[i]가 닫힌 괄호일 경우
            else if (pipes[i] == ')') {
                // 이전 인덱스의 값이 '('일 경우
                if (pipes[i - 1] == '(') {
                    stack.pop();
                    count--;

                    count = count + stack.size();
                    continue;
                }
                // 그 외의 경우
                else {
                    stack.pop();
                }
            }
        }
        // 결과 출력
        System.out.println(count);
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법

• 쇠막대기 문제 풀기위한 핵심 포인트는 (와 )의 짝을 판단하는 것이다. 바로 문제로 들어가 해설을 진행하겠다.

• 가장 먼저 문자열을 입력받아 pipes배열에 넣기 위해 toCharArray메소드를 사용하였다.

  다음으로 Character형의 stack을 선언하고 쇠막대기의 개수를 담을 count변수를 선언한다.

• 반복문은 pipes배열의 길이만큼 반복 수행된다.

  pipes배열의 i번째 값이 (일 경우, stack에 넣고 count의 값을 1 증가시킨다.

  pipes배열의 i번째 값이 )이고 i - 1번째 값이 (일 경우, stack에서 꺼내고 count의 값을 1 감소 시킨다. 그 후 count변수에 stack의 사이즈 만큼 더한다.

  그 외의 경우 stack에서 원소를 꺼낸다.

• 예를 들어 ( ( ( ( )로 들어갔을 경우 )를 만나기 전까지 count의 값은 4가 될 것이고 stack에는 (가 4개 들어가있을 것이다.

  pipes배열의 i번째 값이 )이 되었을 때 stack에서 가장 마지막에 넣은 원소를 제거하고 count의 값을 1 감소 시킨다.

  ()의 모양은 레이저를 의미하기 때문에, stack의 사이즈만큼 count에 더해주어야한다.