1. 괄호 검사란?
괄호 검사는 여는 괄호와 닫는 괄호가 종류와 순서에 맞게 짝을 이루는지 확인하는 문제입니다. 대표적으로 (), [], {}를 검사합니다.
| 문자열 | 판정 | 이유 |
|---|---|---|
{[()]} | 올바름 | 가장 나중에 연 괄호부터 먼저 닫힘 |
([)] | 잘못됨 | [를 연 뒤 )가 먼저 등장하여 종류 불일치 |
((())) | 올바름 | 모든 여는 괄호가 역순으로 닫힘 |
(() | 잘못됨 | 검사 종료 후 여는 괄호가 스택에 남음 |
()) | 잘못됨 | 스택이 빈 상태에서 닫는 괄호가 등장 |
핵심: 괄호는 LIFO(Last In, First Out), 즉 가장 나중에 들어온 것이 가장 먼저 나오는 스택 구조와 정확히 맞습니다.
주어진 기본 코드 상세 설명
def valid_brackets(text):
stack = []
pair = {")": "(", "]": "[", "}": "{"}
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack.pop() != pair[ch]:
return False
return not stack| 코드 | 의미 |
|---|---|
stack = [] | 아직 닫히지 않은 여는 괄호를 저장할 스택 |
pair = {...} | 각 닫는 괄호에 대응하는 올바른 여는 괄호를 딕셔너리로 정의 |
for ch in text | 문자열을 왼쪽에서 오른쪽으로 한 문자씩 검사 |
stack.append(ch) | 여는 괄호를 만나면 스택의 맨 뒤에 삽입 |
not stack | 스택이 비어 있으면 True. 닫는 괄호가 너무 일찍 등장했는지 검사 |
stack.pop() | 가장 최근에 저장한 여는 괄호를 꺼냄 |
pair[ch] | 현재 닫는 괄호와 짝이어야 할 여는 괄호를 얻음 |
return not stack | 모든 검사가 끝난 후 스택까지 비어 있어야 올바른 문자열 |
2. 기초부터 응용까지 예시 코드
예제 1. 소괄호만 검사
def check_parentheses(text):
count = 0
for ch in text:
if ch == "(":
count += 1
elif ch == ")":
count -= 1
if count < 0:
return False
return count == 0
print(check_parentheses("(())")) # True
print(check_parentheses("())(")) # False한 종류의 괄호만 검사할 때는 정수 카운터도 사용할 수 있습니다. 단, 여러 종류의 괄호가 섞이면 종류와 중첩 순서를 기억해야 하므로 스택이 필요합니다.
예제 2. 여러 종류의 괄호 검사
def valid_brackets(text):
stack = []
pair = {")": "(", "]": "[", "}": "{"}
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack:
return False
if stack.pop() != pair[ch]:
return False
return not stack
print(valid_brackets("{[()]}")) # True
print(valid_brackets("([)]")) # False예제 3. 검사 과정을 한 단계씩 출력
def trace_brackets(text):
stack = []
pair = {")": "(", "]": "[", "}": "{"}
for i, ch in enumerate(text):
if ch in "([{":
stack.append(ch)
print(i, ch, "push ->", stack)
elif ch in ")]}":
if not stack:
print(i, ch, "오류: 대응할 여는 괄호 없음")
return False
top = stack.pop()
print(i, ch, "pop", top, "->", stack)
if top != pair[ch]:
print("오류: 괄호 종류 불일치")
return False
if stack:
print("오류: 닫히지 않은 괄호", stack)
return False
return True예제 4. 일반 문자가 섞인 수식 검사
def check_expression(expr):
stack = []
pair = {")": "(", "]": "[", "}": "{"}
for ch in expr:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack.pop() != pair[ch]:
return False
return not stack
print(check_expression("a * (b + c[2])")) # True
print(check_expression("func(a[2} + b)")) # False괄호가 아닌 문자는 아무 동작 없이 건너뜁니다.
예제 5. 오류 위치와 이유 반환
def check_with_reason(text):
stack = []
pair = {")": "(", "]": "[", "}": "{"}
for i, ch in enumerate(text):
if ch in "([{":
stack.append((ch, i))
elif ch in ")]}":
if not stack:
return False, f"{i}번 위치: 여는 괄호가 없습니다."
open_ch, open_i = stack.pop()
if open_ch != pair[ch]:
return False, (
f"{i}번 위치: {open_ch}와 {ch}는 짝이 아닙니다."
)
if stack:
ch, i = stack[-1]
return False, f"{i}번 위치의 {ch}가 닫히지 않았습니다."
return True, "모든 괄호가 올바르게 짝지어졌습니다."예제 6. 괄호의 최대 중첩 깊이 구하기
def max_depth(text):
stack = []
pair = {")": "(", "]": "[", "}": "{"}
maximum = 0
for ch in text:
if ch in "([{":
stack.append(ch)
maximum = max(maximum, len(stack))
elif ch in ")]}":
if not stack or stack.pop() != pair[ch]:
return -1
if stack:
return -1
return maximum
print(max_depth("{[()]}")) # 3정상 문자열이면 최대 스택 크기가 곧 최대 괄호 중첩 깊이입니다.
3. 응용·심화 개념
시간 복잡도와 공간 복잡도
문자열 길이를 n이라 하면 각 문자를 한 번씩 확인하므로 시간 복잡도는 O(n)입니다. 최악의 경우 문자열 전체가 여는 괄호일 수 있으므로 스택 공간은 O(n)까지 필요합니다.
왜 단순 개수 비교만으로는 부족한가?
([)]는 소괄호와 대괄호의 개수는 각각 맞지만 순서가 틀렸습니다. 따라서 여러 종류를 검사하려면 개수뿐 아니라 가장 최근의 여는 괄호 종류를 기억해야 합니다.
스택 불변식
문자열의 앞부분을 어느 지점까지 처리했을 때 스택에는 정확히 아직 닫히지 않은 여는 괄호들이 등장 순서대로 들어 있습니다. 이 성질이 알고리즘의 정확성을 설명하는 핵심입니다.
심화 1. 사용자 정의 괄호 추가
def valid_custom(text):
stack = []
pair = {
")": "(",
"]": "[",
"}": "{",
">": "<"
}
opens = set(pair.values())
for ch in text:
if ch in opens:
stack.append(ch)
elif ch in pair:
if not stack or stack.pop() != pair[ch]:
return False
return not stack심화 2. 모든 오류를 한꺼번에 찾는 방식의 한계
첫 번째 짝 불일치 이후에는 어느 괄호를 기준으로 계속 검사할지 모호해질 수 있습니다. 따라서 문법 검사기는 보통 첫 오류를 보고하거나, 오류 복구 규칙을 별도로 설계합니다.
심화 3. 문자열 리터럴 속 괄호 무시하기
def check_code_line(text):
stack = []
pair = {")": "(", "]": "[", "}": "{"}
quote = None
for ch in text:
if ch in "'\"":
if quote is None:
quote = ch
elif quote == ch:
quote = None
continue
if quote is not None:
continue
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack.pop() != pair[ch]:
return False
return not stack and quote is None실제 Python 소스 전체를 정확하게 분석하려면 이 단순 예제보다 복잡합니다. 이스케이프 문자, 삼중 따옴표, 주석 등을 함께 처리해야 하므로 실제 컴파일러·파서는 토큰화 단계를 사용합니다.
4. 5지선다형 10문항 — 옳은 것 3개 고르기
각 문항에서 반드시 3개를 선택하세요. 문항당 4점, 총 40점.
5. 개념·코드 OX 퀴즈 10문항
문항당 3점, 총 30점.
6. 답이 분명한 단답형 10문항
문항당 3점, 총 30점. 영문은 대소문자를 구분하지 않습니다.
7. 채점 및 결과 저장
아직 채점하지 않았습니다.