[99클럽 코테 스터디 1일차 TIL] 올바른 괄호 문제 풀이와 JDK 21 신기능

프로그래머스 코딩테스트 연습 - 올바른 괄호문제를 보고 풀이한 내용이다.

문제

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

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

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

풀이

이 문제는 스택을 이용해 해결할 수 있었다. 입출력 예를 통해 그림을 그려 살펴보겠다.

비어있는 스택을 하나 만들고, 문자열을 하나씩 받는다. 만약 스택이 비어있고 문자열이 ( 라면 스택에 넣어준다. 스택이 비어있지 않고 문자열이 ) 라면 스택의 가장 최근 요소를 삭제해주면 된다.

결국 스택에 들어가는 요소는 ( 뿐이다. )는 (를 삭제할지 말지 결정하는 값으로 사용된다.

좀 더 복잡한 예제를 살펴보자. 만약 스택이 비어있지 않고 ( 를 넣어줄 차례라면 그대로 쌓아주면 된다. 이후에 )를 만나면 지워지게 된다.

그러나 만약 입출력 예제 3번 )()(과 같이 스택이 비어있는 상태에서 )를 만나면 아예 괄호를 성립할 수 없게 된다. 따라서 그대로 False를 반환해준다.

Python 풀이

Python은 리스트를 곧 스택처럼 사용할 수 있기 때문에 구현이 어렵지 않다.

def solution(s):
    answer = False
    stack = []
    
    for ch in s:
        # 스택이 비어있지 않을 때
        if len(stack) != 0:
            # 괄호가 성립하면 스택에서 지워준다
            if stack[-1] == '(' and ch == ')':
                stack.pop()
            # 성립하지 않으면 스택에 쌓는다
            else:
                stack.append(ch)
        # 스택이 비어있을 때
        else:
            # 닫는 괄호가 들어오면 괄호가 성립할 수 없으므로 즉시 False를 반환한다
            if ch == ')':
                answer = False
                return answer
            # 여는 괄호라면 스택에 쌓는다
            stack.append(ch)
    
    # 스택이 비어있으면 True, 아니면 False 반환
    if stack:
        answer = False
    else:
        answer = True

    return answer

Java 풀이

그러나.. 99클럽에 자바반으로 신청했기 때문에 이제 자바로 문제를 풀어야 하는 위기에 직면했다. 김영한님 강의를 결제하고 자바뽕(?)에 차서 그만.. 갑자기 난이도가 상승한 느낌이지만 한번 도전해보자.

일단 내가 아는 자바 지식을 총동원해서 파이썬과 똑같이 코드를 작성해본다.

import java.util.Stack;

boolean solution(String s) {
        Stack<Character> stack = new Stack();

        for (char item : s.toCharArray()) {
            if (!stack.isEmpty()) {
                if (stack.getLast() == '(' && item == ')') {
                    stack.pop();
                } else {
                    stack.push(item);
                }
            } else {
                if (item == ')') return false;
                stack.push(item);
            }
        }
        return stack.isEmpty();
    }

원래는 이런 코드를 작성했다. 자바에 Stack이라는 클래스가 있다는 걸 처음 알았다. 그런데 프로그래머스에서 자꾸 이런 오류를 뱉었다.

/Solution.java:9: error: cannot find symbol
            if (stack.getLast() == '(' && item == ')') {
                         ^
  symbol:   method getLast()
  location: variable stack of type Stack<Character>
Note: /Solution.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error

잘은 모르겠지만 컴파일러가 getLast() 에 문제가 있다고 콕 찝어주었다. 딱 봐도 마지막 요소를 뽑아주는 메소드인 것 같아서 사용해보려고 했는데.. 왜지? 하고 공식 문서를 살펴봤다! 🔍

JDK 14와 JDK 21의 차이점 발견!

프로그래머스에서 사용하는 JDK 14의 Stack에서 getLast() 메서드를 제공해주고 있지 않았다.

내가 사용하고 있는 JDK 21의 Stack에서는 List 클래스를 통해 getLast() 메서드를 사용할 수 있었던 것이다.

알고보니, Java 21부터 List에 SequencedCollection이라는 인터페이스가 생기면서 제공하는 메소드였다. getLast() 외에도 getFirst(), addFirst(), addList() ... 등의 메서드도 함께 지원하고 있었다.

코드를 살펴보고 싶어서 Ctrl을 누르고 들어가보니 떡하니 써져있는 Since: 21.. 괜히 멀리 갔다. 내부는 제네릭 메서드로 되어있고, get(this.size() - 1) 로 전체 크기에서 마지막 index 값을 가져오도록 하고 있다.

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack();

        for (char item : s.toCharArray()) {
            if (!stack.isEmpty()) {
                if (stack.get(stack.size() - 1) == '(' && item == ')') {
                    stack.pop();
                } else {
                    stack.push(item);
                }
            } else {
                if (item == ')') return false;
                stack.push(item);
            }
        }
        return stack.isEmpty();
    }
}

결국 getLast() 를 사용하던 부분을 stack.get(stack.size() - 1) 로 바꾸어주면서 해결되었다.

done!

스택을 사용하지 않는 방법도 있다던데, 더 생각해보고 추가해 봐야겠다.