[Hackerrank 문제 풀이] Balanced Brackets

Junu Kim·2025년 11월 17일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

38/46

[Stack] Balanced Brackets

난이도: ★★☆☆☆ • solved on: 2025-11-17

문제 요약

문제 유형: 스택(Stack), 문자열 처리
요구사항: 문자열 내 괄호들이 모두 올바르게 짝을 이루는지 판단해야 한다.

사용 개념

자료구조
- Stack : 여는 괄호를 저장하고, 닫는 괄호가 들어올 때 LIFO 구조로 매칭을 확인함
알고리즘/기법
- 스택 기반 괄호 짝 검증
- 순회하며 조건 비교
핵심 키워드
- 유효한 괄호(valid parentheses)
- LIFO 구조
- 매칭 검증

풀이 아이디어

문제 분해

문자열을 왼쪽부터 순차적으로 확인한다.

{, [, ( 는 스택에 push한다.

}, ], ) 는 스택에서 top을 꺼내 (peek) 매칭되는지 비교한다.

중간에 스택이 비거나, 매칭이 불가능한 경우 즉시 "NO" 반환한다.
핵심 로직 흐름
for each char c:
    if 여는 괄호:
        push
    else:
        if stack empty → NO
        if top과 매칭 안 됨 → NO
        pop
순회 종료 후 stack이 비었으면 YES, 아니면 NO
예외 처리

문자열 순회가 끝났는데 스택이 비어 있지 않으면 → 모든 괄호가 닫히지 않은 상태 → "NO" 처리

빈 문자열은 balanced로 간주 (문제 제한 내에서는 등장하지 않음)

코드

public static String isBalanced(String s) {
    Stack<Character> stack = new Stack<>();
    char[] sArray = s.toCharArray();

    for (int i = 0; i < sArray.length; i++) {
        char c = sArray[i];

        // 여는 괄호는 push
        if (c == '{' || c == '[' || c == '(') {
            stack.push(c);
            continue;
        }

        // 닫는 괄호인데 스택이 비어 있으면 오류
        if (stack.isEmpty()) {
            return "NO";
        }

        char top = stack.peek();

        // 괄호 매칭 검사
        if (c == '}' && top != '{') return "NO";
        if (c == ']' && top != '[') return "NO";
        if (c == ')' && top != '(') return "NO";

        // 정상 매칭 → pop
        stack.pop();
    }

    // 모든 괄호 처리 후 스택이 비어 있어야 완전히 balanced
    return stack.isEmpty() ? "YES" : "NO";
}

시간·공간 복잡도

시간 복잡도: O(N)
(문자열을 한 번만 순회)
공간 복잡도: O(N)
(최악의 경우 모든 문자가 여는 괄호일 때 스택에 저장됨)

어려웠던 점

처음에 DelayQueue로 스택을 구현하려 하여 잘못된 방향으로 접근했음. 이전 문제 풀이를 다시 확인하며 Stack 클래스를 사용함을 재확인함. (하지만 동시에 Deque로도 구현이 가능함.)

그렇다면 Deque와 Stack은 어떤 차이가 있는가?

1. 자료구조의 성격

Stack

LIFO(Last In First Out) 전용 구조

한쪽(top)에서만 push/pop 수행

구조적 기능이 제한적

Deque (Double-Ended Queue)

양쪽에서 삽입/삭제 가능

앞(front)에서 add/remove

뒤(back)에서 add/remove

Stack, Queue 모두 구현 가능한 범용 자료구조

2. Java에서의 구현 차이

Stack

java.util.Stack

레거시 클래스

내부적으로 Vector 기반이라 동기화(synchronized)가 걸려 있음
→ 불필요한 오버헤드 존재

최신 Java에서는 사용 비권장

Deque

java.util.Deque

대표 구현체: ArrayDeque, LinkedList

Stack 기능을 대체하는 권장 자료구조

빠르고 가벼우며, thread-safe 오버헤드 없음

배운 점 및 팁

괄호 문제에서는 "순회 중 검증 + 순회 후 스택 비었는지 확인"이 필수 조건임.
자료구조 선택에는 항상 어떤 클래스를 객체로 생성할 수 있는가를 아는게 중요하며, LIFO가 필요한 상황에서는 Stack 또는 Deque을 이용해야 함.

참고 및 링크

문제 링크: https://www.hackerrank.com/challenges/balanced-brackets/problem
참고 블로그/깃허브: 없음

추가 연습 문제

비슷한 유형 (GPT 추천) :
- Valid Parentheses (LeetCode 20)
- 괄호 제거(BOJ 2800)
- 스택 수열(BOJ 1874)
확장 문제 (GPT 추천) :
- 태그 구조가 올바른지 확인하는 XML/HTML validator 구현
- 중첩된 구조 파싱 문제(예: 수식 파싱)