문제 보기 · Level 2 · 2020 KAKAO BLIND RECRUITMENT · 정답률 49% · 푼 사람 21,857명 (2026-09-30 기준)1

문제

’(‘와 ‘)’의 개수가 같은 문자열 p를 문제가 정한 재귀 절차로 짝이 맞는 괄호 문자열로 바꾼다.

  1. 빈 문자열이면 빈 문자열을 돌려준다.
  2. p를 더 쪼갤 수 없는 균형 문자열 u와 나머지 v로 나눈다.
  3. u가 짝이 맞으면 u 뒤에 v의 변환 결과를 붙여 돌려준다.
  4. 짝이 맞지 않으면 ‘(‘ + v의 변환 결과 + ‘)’를 만들고, 그 뒤에 u의 양 끝을 떼고 나머지 괄호 방향을 뒤집은 것을 붙여 돌려준다.
  • p 길이 2~1,000, 짝수

풀이

막히면 한 단계씩 펼친다.

필요한 개념
  • 재귀와 백트래킹: 문제의 절차가 이미 재귀다. 그대로 옮긴다.
  • 스택: 짝이 맞는지 확인하기. 여기서는 스택 대신 “지금까지 연 괄호 수” 하나로 센다.
  • 재귀적 정의와 구조적 귀납법: 올바른 문자열은 그 문서의 ‘균형 괄호’(빈 문자열, (s), st 세 규칙으로 만든 것)다. 이 문서의 균형 문자열(개수만 같음)과는 뜻이 다르다. 변환 결과가 늘 올바른 것도 길이에 대한 귀납법으로 보인다. 변환(v)가 올바르다고 두면, u가 올바를 때 결과는 규칙 st다. 아니면 u는 ‘)’로 시작한다. ‘(‘를 +1, ‘)’를 −1로 센 값은 끝에서야 0이 되므로, 가운데에서는 내내 음수다. 그래서 양 끝을 떼고 뒤집은 가운데는 올바르다. ‘(‘ + 변환(v) + ‘)’는 규칙 (s)이고, 그 뒤에 이것을 붙인 결과도 규칙 st다.
1단계 · 작은 예로 손으로 풀기

용어부터 정리한다. 균형 문자열은 ‘(‘와 ‘)’의 개수만 같은 것, 올바른 문자열은 짝까지 맞는 것이다.

p = "))(("

  1. 앞에서부터 세며 처음으로 개수가 같아지는 곳에서 자른다: ) → −1, ) → −2, ( → −1, ( → 0. 끝까지 가서야 0이니 u = "))((", v = ""
  2. u는 올바르지 않다(처음부터 ‘)’)
  3. ’(‘ + 변환(v) + ‘)’ = "()"
  4. u의 양 끝을 떼면 ")(", 방향을 뒤집으면 "()"
  5. 합치면 "()()"

“뒤집기”는 글자 순서를 거꾸로 하는 게 아니라, 글자마다 ( ↔ )를 바꾸는 것이다.

2단계 · 가장 단순한 방법과 그 속도

절차를 그대로 따르는 것이 곧 답이다. 한 번 부를 때마다 u를 찾느라 문자열을 훑고, 부를 때마다 v가 적어도 두 글자 짧아진다. 길이 1,000이면 호출이 많아야 500번, 전체 훑기는 50만 번 정도다. 재귀 깊이도 500 이하라 파이썬 한도(1,000) 안이다.

3단계 · 핵심 아이디어

도우미 둘만 만들면 절차를 한 줄씩 옮길 수 있다.

  • u, v 나누기: 앞에서부터 ‘(‘면 +1, ‘)’면 −1을 더한다. 처음으로 0이 되는 자리까지가 u다. 그보다 앞에서 0이 된 적이 없으니 “더 쪼갤 수 없는” 균형 문자열이다.
  • 올바른지 확인: 같은 방식으로 더하다가 한 번이라도 음수가 되면 올바르지 않다. 닫는 괄호가 여는 괄호보다 먼저 많아진 것이다.
4단계 · 코드 흐름
  1. p가 비었으면 빈 문자열.
  2. 개수를 세며 u, v로 나눈다.
  3. u가 올바르면 u + 변환(v).
  4. 아니면 “(“ + 변환(v) + “)” + (u의 양 끝을 뗀 뒤 글자마다 뒤집은 것).
5단계 · 파이썬 코드 
def is_correct(s):
    bal = 0
    for ch in s:
        bal += 1 if ch == "(" else -1
        if bal < 0:                       # 닫는 괄호가 먼저 많아졌다
            return False
    return bal == 0

def solution(p):
    if p == "":                           # 1
        return ""
    bal = 0
    for i, ch in enumerate(p):            # 2. 처음 균형이 맞는 곳에서 자른다
        bal += 1 if ch == "(" else -1
        if bal == 0:
            u, v = p[:i + 1], p[i + 1:]
            break
    if is_correct(u):                     # 3
        return u + solution(v)
    flipped = "".join("(" if ch == ")" else ")" for ch in u[1:-1])
    return "(" + solution(v) + ")" + flipped   # 4
  • 1 if ch == "(" else -1: 여는 괄호면 1, 닫는 괄호면 −1이다.
  • u[1:-1]: 첫 글자와 마지막 글자를 뗀다.
  • "".join(… for ch in …): 글자마다 바꾼 뒤 이어 붙인다.
  • solution(v): 문제의 “1단계부터 다시 수행”이 곧 재귀 호출이다.
6단계 · 실행 추적

p = "()))((()"

호출 u v u가 올바른가 결과
f(“()))((()”) ”()” ”))((()” 예 ”()” + f(“))((()”)
f(“))((()”) ”))((“ ”()” 아니오 ”(“ + f(“()”) + “)” + 뒤집기(“)(“)
f(“()”) ”()” ”” 예 ”()” + f(“”) = “()”

가운데 줄: “(“ + “()” + “)” + “()” = “(())()”. 맨 위: “()” + “(())()” = "()(())()"

7단계 · 복잡도와 흔한 실수

호출마다 문자열을 훑으니 \(O(n^2)\) 이하다(n ≤ 1,000).

  • “뒤집기”를 글자 순서 거꾸로(u[1:-1][::-1])로 한다. 글자마다 ( ↔ )를 바꿔야 한다.
  • u를 “가장 짧은” 균형 문자열이 아니라 더 길게 자른다.
  • 4단계에서 v를 변환하지 않고 그대로 붙인다.
검증: 문제의 예시 3개를 통과했다. 길이 12 이하의 모든 균형 문자열(1,274개)에서 결과가 늘 올바른 괄호 문자열이고, 입력이 이미 올바르면 그대로 돌아오는 것을 확인했다 — 17_pg60058_p1.py

  1. 프로그래머스 스쿨, “괄호 변환” (https://school.programmers.co.kr/learn/courses/30/lessons/60058), 2026-09-30 조회. ↩