올바른 괄호 판별

문제 개요

문자열 s가 다음 조건에 따라 올바른 괄호인지 확인하는 문제입니다.
'('로 열린 괄호는 반드시 ')'로 닫혀야 합니다.
닫는 괄호가 여는 괄호보다 먼저 나오면 안 됩니다.
모든 괄호를 처리한 후, 여는 괄호가 남아있으면 안 됩니다.

제약사항:
문자열 길이 ≤ 100,000
문자열은 '('와 ')'로만 이루어져 있습니다.

문제 접근

이 문제는 여는 괄호와 닫는 괄호의 개수를 비교하며 해결할 수 있습니다.

핵심 아이디어
문자열을 순회하면서 여는 괄호 '('의 개수를 증가시키고, 닫는 괄호 ')'의 개수를 감소시킵니다.
순회 중간에 여는 괄호보다 닫는 괄호가 많아지면, 올바르지 않은 괄호 문자열입니다.
순회가 끝난 후, 여는 괄호의 개수가 0이 아니라면 올바르지 않은 문자열입니다.

코드 구현

import Foundation

func solution(_ s: String) -> Bool {
    var openCount = 0  // 여는 괄호 '('의 개수를 추적

    for char in s {
        if char == "(" {
            openCount += 1  // 여는 괄호인 경우 개수 증가
        } else {
            openCount -= 1  // 닫는 괄호인 경우 개수 감소
        }

        // 닫는 괄호가 여는 괄호보다 많아진 경우
        if openCount < 0 {
            return false
        }
    }

    // 모든 괄호를 처리한 후 여는 괄호가 남아있으면 false
    return openCount == 0
}

코드 설명

1. 여는 괄호 개수 추적
openCount는 여는 괄호의 개수를 저장하는 변수입니다.
문자열을 순회하면서 여는 괄호는 +1, 닫는 괄호는 -1을 수행합니다.
2. 중간 검증
순회 중간에 openCount < 0이면, 닫는 괄호가 여는 괄호보다 많아진 상태입니다.
이 경우, 올바른 괄호 문자열이 아니므로 바로 false를 반환합니다.
3. 최종 검증
순회가 끝난 후 openCount == 0이어야 올바른 괄호입니다.
그렇지 않으면 여는 괄호가 더 남아있는 상태이므로 false를 반환합니다.

입출력 예시 및 설명

입력 1

let s = "()()"
print(solution(s)) // true

과정:
openCount 변화: +1, -1, +1, -1 → 최종 값: 0
결과: 올바른 괄호.

입력 2

let s = "(())()"
print(solution(s)) // true

과정:
openCount 변화: +1, +1, -1, -1, +1, -1 → 최종 값: 0
결과: 올바른 괄호.

입력 3

let s = ")()("
print(solution(s)) // fals

과정:
openCount 변화: -1 → false (중간에 닫는 괄호가 더 많아짐)
결과: 올바르지 않은 괄호.

입력 4

let s = "(()("
print(solution(s)) // false

과정:
openCount 변화: +1, +1, -1, +1 → 최종 값: 1 (여는 괄호가 남음)
결과: 올바르지 않은 괄호.

시간 복잡도

순회:
문자열을 한 번 순회하며 각 문자를 처리하므로 O(n).
공간 복잡도:
openCount는 단일 정수 변수로, O(1).

학습 포인트

문자열 순회와 상태 추적:
문자열을 순회하며 특정 조건(openCount)을 상태로 유지하고 적절히 업데이트하는 방법을 익혔습니다.
빠른 종료 조건:
불필요한 추가 연산을 방지하기 위해 중간에 조건(openCount < 0)을 만족하면 바로 종료합니다.
효율적인 처리:
O(n)의 시간 복잡도로 제한 조건(최대 100,000 길이)을 만족하는 솔루션을 작성할 수 있었습니다.

느낀 점

이 문제는 자료구조(Stack)를 이용한 풀이가 흔히 소개되지만, 단일 카운트 변수를 사용하여 더 간단하고 효율적으로 풀 수 있음을 알게 되었습니다. 효율성과 간결함을 모두 잡은 해결책을 설계하는 연습이 되었습니다