[알고리즘]프로그래머스 12909번 - 올바른 괄호

프로그래머스 12909번 - 올바른 괄호

프로그래머스 12909번 - https://programmers.co.kr/learn/courses/30/lessons/12909

 

요구사항

1. '(' 문자로 괄호가 열렸으면 반드시 짝지어서 ')' 문자로 괄호가 닫혀야 한다.

2. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때 올바른 괄호인지를 반환하라.

3. 올바른 괄호인 경우 true, 잘못된 괄호인 경우 false

 

요구사항 분석 및  풀이과정

1. 문자열의 문자 배열을 순회하여 '('를 만나면 스택에 넣는다. - ')'이 나타나면 짝을 맞춰 삭제해주기 위해서 보관합니다.

2-1. ')'를 만나면 스택의 가장 위의 원소가 '('이면 정상적으로 짝이 맞으므로 삭제하여준다.

2-2. 만약 스택이 비었거나, 가장 위의 원소가 '('이 아니라면 짝이 맞지 않는 잘못된 괄호 문자열(false)이다.

3. 또한 모든 작업을 마쳤는데 스택에 문자가 남아있는 경우는 짝의 개수가 맞지 않아 제거되지 못한 것이므로 잘못된 괄호 문자열(false)이다.

 

'('를 "스택"에 넣어주는 이유는 가장 나중에 나온 '(' 문자는 가장 먼저 나온 ')'와 짝이 맞아야 하기 때문입니다.

 

올바른 괄호 문자열인 경우

 

잘못된 괄호 문자열인 경우

소스코드 작성

import java.util.ArrayDeque;

class Solution {

    public boolean solution(String s) {
        char[] chars = s.toCharArray();
        ArrayDeque<String> stack = new ArrayDeque<>();
        
        for(char v : chars) {
            if (v == ')') {
                if (!stack.isEmpty() && stack.peekLast().equals("(")) {
                    stack.pollLast();
                    continue;
                }
                
                return false;
            }
            
            stack.offerLast(String.valueOf(v));
        }
        
        return stack.isEmpty() ? true : false;
    }
}

 

결과

 

소스코드 깃허브 주소

링크

 

마무리

사실상 스택을 쓰지 않아도, '(' 괄호의 수와 ')' 괄호의 수 계산하여 풀어도 풀 수 있다. 하지만 나는 처음에 괄호 문제라서 전형적인 스택 문제라고 생각했고, 스택을 사용했다. 조금만 더 생각을 했더라면 굳이 스택까지 쓸 필요는 없었을 것 같다는 생각이 들지만, 스택을 이용한 방법도 충분히 의미가 있다고 생각한다.