자바 코딩테스트 강좌, 스택과 큐

문제 1: 유효한 괄호

주어진 문자열이 유효한 괄호 문자열인지 확인하는 문제입니다.
유효한 괄호 문자열은 열린 괄호가 닫힌 괄호로 올바르게 닫히고, 올바른 순서를 가진 경우를 가리킵니다.
예를 들어, “()”, “()[]{}”, “{[()]}”는 유효하지만, “(]”, “([)]”, “{)”은 유효하지 않습니다.

문제 설명

입력으로 주어진 문자열 s가 유효한 괄호 문자열인지 판단하는 함수를 구현하시오.
유효한 괄호 문자열은 다음 조건을 만족해야 합니다:

모든 열린 괄호는 반드시 닫힌 괄호와 쌍을 이루어야 한다.
열린 괄호는 올바른 순서로 정렬되어 있어야 한다.

입력 예시

“()” -> true
“()[]{}” -> true
“{[()]}” -> true
“(]” -> false
“([)]” -> false
“{)” -> false

해결 방법

본 문제는 스택을 이용하여 해결할 수 있습니다.
스택(FILO: First In Last Out) 구조는 괄호의 연산에서 매우 유용합니다. 진행 과정은 다음과 같습니다.

문자열을 왼쪽부터 오른쪽으로 탐색합니다.
열린 괄호((, {, [)를 만나면 스택에 push합니다.
닫힌 괄호(), }, ])를 만나면 스택에서 pop하여 가장 최근에 열린 괄호와 쌍을 이루는지 확인합니다.
모든 문자열을 처리한 후, 스택이 비어있다면 유효한 괄호 문자열로 판단합니다.

자바 코드 구현

            
            import java.util.Stack;

            public class ValidParentheses {
                public static boolean isValid(String s) {
                    Stack stack = new Stack<>();
                    for (char c : s.toCharArray()) {
                        if (c == '(' || c == '{' || c == '[') {
                            stack.push(c);
                        } else {
                            if (stack.isEmpty()) return false;
                            char top = stack.pop();
                            if ((c == ')' && top != '(') || 
                                (c == '}' && top != '{') || 
                                (c == ']' && top != '[')) {
                                return false;
                            }
                        }
                    }
                    return stack.isEmpty();
                }

                public static void main(String[] args) {
                    System.out.println(isValid("()")); // true
                    System.out.println(isValid("()[]{}")); // true
                    System.out.println(isValid("{[()]}")); // true
                    System.out.println(isValid("(]")); // false
                    System.out.println(isValid("([)]")); // false
                    System.out.println(isValid("{)")); // false
                }
            }

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n)입니다.
n은 문자열의 길이입니다. 스택을 사용하는 만큼 최악의 경우 열린 괄호가 n개 있을 때 n번의 push와 n번의 pop 연산이 이루어질 수 있습니다.

공간 복잡도

공간 복잡도 또한 O(n)입니다.
스택에 최대 n개의 열린 괄호가 들어갈 수 있으므로 최악의 경우 공간 복잡도는 O(n)입니다.

문제 풀이 과정 요약

본 문제를 해결하기 위해 스택을 사용하여 열린 괄호를 추적하고, 닫힌 괄호가 나올 때마다 스택에서 pop하여 검사하는 방법을 사용했습니다.
이러한 방법은 괄호의 유효성을 검사하는 데 있어 매우 효율적이며, 다른 괄호에 대한 유효성 검사에도 동일한 원리를 적용할 수 있습니다.

유효한 코딩 테스트를 위한 팁

코딩 테스트에서 스택과 큐는 자주 활용되는 자료구조입니다.
다양한 문제를 통해 스택과 큐의 활용 방법과 그 리듬에 익숙해지는 것이 중요합니다.
자주 등장하는 패턴과 트릭을 익히고, 다양한 변형 문제를 연습하여 문제 해결 능력을 키우세요.