[프로그래머스] 올바른 괄호 - 자바(Java)

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=java

프로그래머스

 

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

 

코드

import java.util.ArrayDeque;

class Solution {
    boolean solution(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
       
        char[] a = s.toCharArray();
        for(char c : a) {
            if(c == '(') {
                stack.push(c);
            }else {
                if(stack.isEmpty() || stack.pop() == c)
                    return false;
            }
        }
        
        return stack.isEmpty();
    }
}

 

정리

이런 괄호 짝 맞추기를 해결하려면 프로그래머스에도 스택/큐 라고 분류되어 있는데 스택을 사용하면 됩니다.

닫힌 괄호가 임의 위치의 열린 괄호와 상쇄되는 것이 아니라 닫힌 괄호가 나오기 바로 전의, 즉 가장 가까운 (최근) 열린 괄호와 상쇄된다는 겁니다.

1. 문자열을 앞에서 하나씩 보며 열린 괄호가 나오면 푸시

2. 닫힌 괄호가 나오면 팝 연산을 통해 문자열에서 열린 괄호, 닫힌 괄호 한 쌍을 상쇄

3. 1~2를 마지막 문자열까지 반복해 스택에 열린 괄호가 남아 있다면 짝이 맞지 않는 것은(false), 괄호가 남아 있지 않다면 짝이 맞는 것(true)로 판한 합니다.