[백준 10799/자바(java)] 쇠막대기

백준(baekjoon) 10799 쇠막대기

이 문제는 스택을 활용하여 푸는 문제이다. 자바에서는 ArrayDeque도 있기에 둘 중 편한 방법으로 풀이하면 된다.

 

1. Stack

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();
        int answer = 0;
        Stack<Character> stack = new Stack<>();

        char[] arr = s.toCharArray();
        for (int i = 0 ; i < arr.length ; i++) {
            char x = arr[i];
            if (x == '(') {
                stack.push(x);
            } else {
                char prev = arr[i - 1];
                if (prev == '(') {
                    stack.pop();
                    answer += stack.size();
                } else {
                    stack.pop();
                    answer += 1;
                }
            }
        }
        System.out.println(answer);
    }
}

풀이과정

'('일 때는 스택에 더해주고, "()" 이렇게 한 쌍이 되는 순간 레이저가 되므로 ')'일 때, 바로 직전의 입력이 '('이면 stack.pop()을 하고 answer에 stack.size()를 더해준다. 그리고 직전의 입력이 '('이 아닐 때 ')'이 입력되는 경우에는 레이저가 닫히는 것이므로 answer에 1을 더해준다.

 

2. ArrayDequeue

이것도 선언만 ArrayDequeue로 바꾸고, 코드 내용은 똑같다.

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();
        int answer = 0;
        ArrayDeque<Character> stack = new ArrayDeque<>();

        char[] arr = s.toCharArray();
        for (int i = 0 ; i < arr.length ; i++) {
            char x = arr[i];
            if (x == '(') {
                stack.push(x);
            } else {
                char prev = arr[i - 1];
                if (prev == '(') {
                    stack.pop();
                    answer += stack.size();
                } else {
                    stack.pop();
                    answer += 1;
                }
            }
        }
        System.out.println(answer);
    }
}