🧩 괄호 문자열 문제 접근법 정리 (Counter vs Stack 완전 이해)

---

🎯 문제 요약

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때,
괄호가 올바르게 짝지어져 있으면 true, 아니면 false를 반환하라.

예시

"()()"     → true
"(())()"   → true
")()("     → false
"(()("     → false

조건

• 문자열 길이 ≤ 100,000
• '(', ')' 만 포함됨

---

🧠 접근 방향

이 문제의 핵심은
👉 열린 괄호 '('와 닫힌 괄호 ')'의 균형을 맞추는 것입니다.
즉, 여는 괄호가 나오면 반드시 닫혀야 하며,
닫는 괄호가 나올 때는 이미 열린 괄호가 있어야 합니다.

이를 해결하는 대표적인 두 가지 방식이 있습니다:

1. 카운터 방식 (Counter)
2. 스택 방식 (Stack)

---

🧮 1️⃣ 카운터 방식

✅ 아이디어

• '(' → +1
• ')' → -1
• 도중에 카운터가 음수가 되면 → ❌ (닫는 괄호가 너무 일찍 나옴)
• 문자열이 끝났을 때 카운터가 0이 아니면 → ❌ (열린 괄호가 남음)

---

📊 예시

"(()())"

문자	동작	카운터 값
(	+1	1
(	+1	2
)	-1	1
(	+1	2
)	-1	1
)	-1	0

✅ 도중에 음수가 없고, 마지막에 0이므로 올바른 괄호.

---

✅ 시간 복잡도

• 문자열 한 번만 순회 → O(n)
• 변수 하나만 사용 → 공간복잡도 O(1)

---

💡 장점

• 코드가 매우 간단함
• 괄호처럼 단순한 짝 검증 문제에 적합

---

📦 2️⃣ 스택(Stack) 방식

✅ 스택이란?

한쪽 끝에서만 데이터를 넣고(push) 빼는(pop) 선형 자료 구조
“마지막에 넣은 게 먼저 나온다” → LIFO (Last In, First Out)

쉬운 비유:
📚 “접시 쌓기”

• 접시를 위에 차곡차곡 쌓고,
• 꺼낼 땐 맨 위(가장 최근)에 올린 접시부터 꺼냄.

---

✅ 왜 괄호 문제에 스택을 쓰는가?

괄호의 규칙이 바로 LIFO 구조이기 때문입니다.

• 여는 괄호 '(' → push
• 닫는 괄호 ')' → pop (최근 열린 괄호와 짝을 지음)

가장 최근에 열린 괄호가 가장 먼저 닫히기 때문입니다.

---

📊 예시 "(()())"

단계	문자	동작	스택 상태
1	(	push(1)	[1]
2	(	push(2)	[1, 2]
3	)	pop → 2 제거	[1]
4	(	push(4)	[1, 4]
5	)	pop → 4 제거	[1]
6	)	pop → 1 제거	[]

✅ 마지막에 스택이 비었으면 모든 괄호가 올바르게 닫힘.
❌ 도중에 pop할 게 없으면 (스택이 비어있는데 닫힘이 나왔으면) 잘못된 괄호.

---

✅ 시간 복잡도

• 문자열 한 번만 순회 → O(n)
• push/pop은 상수 시간 → O(1)
• 스택에 최대 n개 쌓일 수 있음 → 공간복잡도 O(n)

---

💡 정리

구분	카운터 방식	스택 방식
아이디어	열린 괄호 개수를 숫자로 세기	열린 괄호를 스택에 쌓고 닫히면 꺼냄
시간 복잡도	O(n)	O(n)
공간 복잡도	O(1)	O(n)
장점	코드 간단, 효율적	중첩 구조 추적에 유리
사용 예시	괄호 짝 검증	괄호, HTML 태그, 함수 호출 추적 등

---

⚙️ 3️⃣ 시간 복잡도란?

알고리즘이 입력 크기(n)에 따라 얼마나 오래 걸리는지를 표현하는 척도.

표기	의미	예시
O(1)	입력 크기와 상관없이 일정한 시간	단순 계산 (a+b)
O(n)	입력 크기만큼 반복	문자열/배열 한 번 순회
O(n²)	이중 반복	중첩 for문
O(log n)	절반씩 줄이는 탐색	이진 탐색

➡ 이 문제는 문자열을 한 번만 확인하므로 O(n) 이다.

---

🧾 최종 요약

항목	핵심 요약
문제 핵심	열린 괄호와 닫힌 괄호의 균형 확인
카운터 방식	간단 + 효율적 (O(n), O(1))
스택 방식	순서 추적에 강함 (O(n), O(n))
공통점	둘 다 시간 효율은 동일
추천 방식	단순 괄호 문제 → 카운터, 중첩 구조 문제 → 스택

---

✏️ 한 줄 정리

괄호 검증은 “열고 닫는 순서 추적” 문제이며,
카운터는 “갯수 기반”, 스택은 “순서 기반” 접근이다.
효율성은 같지만, 상황에 따라 도구를 다르게 쓰면 된다.

---