[코딩 테스트 Java] 스택 ❷ – 몸풀기 문제

지금까지 배운 내용을 활용해서 문제 2개를 풀어보겠습니다. 여기서는 왜 스택을 사용하는지, 스 택을 어떤 식으로 활용하는지에 집중하며 학습하기 바랍니다. 깃허브 코드를 확인해주세요.

문제 01 올바른 괄호 ⭐️⭐️

저자 권장 시간_30분
권장 시간 복잡도_O(N)
출제_스택/큐
문제 URL_https://school.programmers.co.kr/learn/courses/30/lessons/12909
정답 URL_ https://github.com/retrogemHK/codingtest_java/blob/main/solution/08.java

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

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

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

제약 조건

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

입출력의 예

01단계

다음은 짝이 맞지 않는 괄호의 예입니다. 한눈에 봐도 괄호의 짝이 맞지 않습니다. 닫힌 괄호가 먼저 왔으므로 더 이상 상쇄가 되지 않으며, 결과적으로 괄호가 전부 없어지지 않습니다.

02단계

다른 예도 봅시다. 이 역시도 괄호의 짝이 맞지 않습니다. 첫 괄호의 짝은 맞아 상쇄할 수 있지만 마지막 괄호는 짝이 없으므로 상쇄할 수 없습니다.

03단계

그러면 이번에는 괄호의 짝이 맞아 모두 상쇄되는 예를 봅시다. 다음의 경우 괄호의 짝이 맞아서 상쇄되어 모두 사라졌습니다.

04단계

이 경우도 괄호의 짝이 맞는 경우입니다. 그림에서 보듯 항상 첫 번째 짝만 괄호가 맞아야 할 필요는 없습니다.

문제 분석하고 풀기

이런 괄호 짝 맞추기를 해결하려면 어떻게 해야 할까요? 바로 스택을 사용하면 됩니다. 스택을 어떻게 적용할 수 있는지 알아보겠습니다. 여러분이 문제 조건에서 주목해야 할 내용은 **닫힌 괄호가 임의 위치의 열린 괄호와 상쇄되는 것이 아니라 닫힌 괄호가 나오기 바로 전의, 즉 가장 가까운(최근) 열린 괄호와 상쇄된다는 겁니다. 가장 가까운(최근)**이라는 키워드를 보고 스택을 떠올리는 감각이 있어야 합니다. 스택과 함께 이 문제를 풀려면 다음과 같은 과정으로 괄호를 상쇄하면 됩니다.

문자열을 앞에서 하나씩 보며 열린 괄호가 나오면 푸시
닫힌 괄호가 나오면 팝 연산을 통해 문자열에서 열린 괄호, 닫힌 괄호 한 쌍을 상쇄
1~2를 마지막 문자열까지 반복해 스택에 열린 괄호가 남아 있다면 짝이 맞지 않은 것(false)이고, 괄호가 남아 있지 않다면 짝이 맞은 것(true)으로 판단

실제 데이터와 함께 위 과정을 연습해봅시다.

괄호의 짝이 맞는 경우

01단계

우선은 짝이 맞는 경우를 봅시다. ➊ 크기가 6인 배열에 괄호를 배치하고 스택을 준비합니다. ➋ 그런 다음 인덱스 0은 열린 괄호이므로 스택에 푸시하고 다음을 봅니다. ➌ 다음의 값은 닫힌 괄호이므로 스택에서 팝하고 다음을 봅니다. 이 단계를 마치면 스택에는 아무것도 없으므로 지금까지 본 인덱스 0~1에 한해서는 괄호를 상쇄했다고 보아도 됩니다.

02단계

➊ 인덱스 2는 열린 괄호이므로 푸시하고 다음을 봅니다. ➋ 인덱스 3은 열린 괄호이므로 다시 푸시하고 다음을 봅니다. ➌ 이번엔 닫힌 괄호이므로 스택에서 팝하고 다음을 봅니다. ➍ 인덱스 5는 닫힌 괄호이므로 팝하고 연산을 마칩니다. 모든 탐색을 끝냈을 때 스택이 비어 있으므로 배열의 괄호는 모두 짝이 맞습니다.

괄호의 짝이 맞지 않는 경우

01단계

이번엔 짝이 맞지 않은 경우를 봅니다. ➊ (, ), ( 순서로 괄호가 배치되어 있습니다. ➋ 처음은 열린 괄호이므로 푸시하고 그다음을 봅니다.

02단계

➌ 인덱스 1은 닫힌 괄호이므로 팝하고 다음을 봅니다. ➍ 인덱스 2는 열린 괄호이므로 푸시합니다. 이렇게 하고 보면 모든 데이터를 탐색했으므로 스택에는 열린 괄호가 남아 있습니다. 즉, 짝이 맞지 않습니다.

이제 코드로 문제를 풀어봅니다. 코드는 아주 간단합니다.


import java.util.ArrayDeque;

class Solution {

  private 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();
  }
}

❶ stack.isEmpty( )로 스택이 비어있는지 먼저 체크한 후 pop( )하고 있는 것을 주목하세요. 스택이 비어있을 때 pop( ) 메서드를 호출하면 EmptyStackException 예외가 발생합니다.

시간 복잡도 분석하기

N은 s의 길이입니다. s를 순회하며 괄호의 쌍을 확인하므로 시간 복잡도는 O(N)입니다. 참고로 괄호 쌍을 확인할 때 push( ) 메서드와 pop( ) 메서드의 시간 복잡도는 O(1)입니다.