[프로그래머스 코딩테스트] 올바른 괄호(Java)

  문제 설명

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

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

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

 

  제한사항

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

 

  입출력 예

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

import java.util.Stack;
class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();
        for (char c: s.toCharArray()) {
            if (stack.isEmpty() || c == '(') {
            stack.push(c);
            } else {
                stack.pop();
            }
        }
        if (!stack.isEmpty()) {
            answer = false;
        }
        return answer;
    }
}

  이번에는 데크로 먼저 풀었지만, 문제에서 '스택/큐'라고명시되어 있으므로 스택 풀이를 먼저 하겠습니다.

  answer를 생성하고 초기화 값은 true입니다. Stack을 생성하고 제네릭 타입은 Character로 지정합니다.

  for-each문에서 toCharArray 메소드를 이용하여 문자열 s를 문자 형태의 배열 타입으로 만들고 문자 c는 이를 하나씩 받습니다.

  첫 번째 if문에서 스택이 비어있거나, 또는 c가 여는 괄호일 경우 push 메소드를 이용하여 stack에 c를 추가합니다. 만약 앞선 조건에 해당하지 않는다면, 예를 들어 스택이 비어있지 않고 동시에 c가 닫는 괄호일 경우에는 pop 메소드를 이용하여 스택의 맨 위 원소를 제거합니다.

  두 번째 if문에서 만약 스택이 비어있지 않다면 answer에 false를 할당합니다.

  문제 자체는 간단한 편이지만 효율성 테스트가 깐깐한 편입니다. 여러 시도를 해보았으나 String형을 char형으로 바꾸어 비교하는 것으로 허무하리만치 간단히 풀렸습니다.

  다음은 Deque를 이용한 풀이입니다. 이 역시 효율성 테스트를 통과해보기 위한 대안 중 하나였습니다. Deque 역시 평소의 풀이로는 풀리지 않았고, 스택과 마찬가지로 문자열을 문자로 바꾸어 풀어야만 풀렸습니다. 다른 대안이 있을 수도 있겠지만 문자로 변경하여 풀이하는 방법이 가장 간편한 것 같습니다.

 

import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Deque<Character> deque = new ArrayDeque<>();
        for (char c: s.toCharArray()) {
            if (deque.isEmpty() || c == '(') {
            deque.addLast(c);
            } else if (!deque.isEmpty() && c == ')') {
                deque.removeLast();
            }
        }
        if (!deque.isEmpty()) {
            answer = false;
        }
        return answer;
    }
}

  데크는 스택을 이용하여 푸는 방식과 동일합니다. 다만 두 자료구조는 동일한 기능에도 메소드명의 차이가 있습니다. 또 스택은 단방향, 데크는 양방향이라는 특징이 있어 데크를 이용할 경우에는 방향의 구분이 필요합니다.