문제 출처 : 프로그래머스
난이도 : Level 2

---

문제 파악

이 문제를 처음 읽었을 때 가장 헷갈렸던 건
‘균형잡힌 괄호 문자열’과 ‘올바른 괄호 문자열’의 차이였다.

• 균형잡힌 괄호 문자열

  • '(' 개수와 ')' 개수가 같기만 하면 된다
  • 순서는 중요하지 않다
  • 예: "))((", "(()())"

• 올바른 괄호 문자열

  • 왼쪽부터 봤을 때 ')'가 먼저 나오면 안 된다
  • 끝났을 때 괄호 개수도 정확히 맞아야 한다
  • 예: "(()())()"

이 문제는
👉 균형만 맞는 문자열을, 올바른 괄호 문자열로 변환하는 문제다.

---

해결 아이디어

이 문제는 아이디어를 새로 떠올리는 문제가 아니라
문제에서 제시한 알고리즘(1~4단계)을 그대로 구현하는 문제다.

전체 흐름은 다음과 같다.

1. 입력이 빈 문자열이면 그대로 반환
2. 문자열을 u, v로 분리
   • u는 더 이상 분리할 수 없는 가장 앞쪽의 균형잡힌 문자열
3. u가 올바른 괄호 문자열이면
   • u 뒤에 solution(v)를 붙여서 반환
4. u가 올바르지 않다면
   • "(" + solution(v) + ")"
   • u의 앞뒤를 제거한 뒤 괄호 방향을 뒤집어서 뒤에 붙인다

---

핵심 포인트 1 : u, v 분리

문제에서 말하는
“u는 더 이상 분리할 수 없는 균형잡힌 괄호 문자열”의 의미는,

왼쪽부터 문자를 보면서
'('는 +1, ')'는 -1
처음으로 합이 0이 되는 지점까지가 u

라는 뜻이다.

그래서 balance가 처음 0이 되는 순간 바로 끊어야 한다.

---

핵심 포인트 2 : u가 올바른 괄호인지 판단

스택을 쓰지 않아도 된다.

왼쪽부터 보면서

• '(' → +1
• ')' → -1

을 했을 때,
중간에 한 번이라도 음수가 되면 올바르지 않은 괄호 문자열이다.

---

핵심 포인트 3 : 4단계 조립 순서

u가 올바르지 않은 경우 결과 문자열은 항상 아래 형태다.

"( solution(v) )" + 뒤집은(u의 내부)

여기서 순서를 헷갈리면 오답이 된다.
반드시 앞에 괄호로 감싼 문자열을 만들고, 그 뒤에 뒤집은 u를 붙인다.

---

최종 코드

def split_uv(w):
    balance = 0
    for i, c in enumerate(w):
        if c == '(':
            balance += 1
        else:
            balance -= 1
        if balance == 0:
            return w[:i+1], w[i+1:]


def solution(p):
    if p == "":
        return ""

    u, v = split_uv(p)

    # u가 올바른 괄호 문자열인지 확인
    balance = 0
    is_correct = True
    for c in u:
        balance += 1 if c == '(' else -1
        if balance < 0:
            is_correct = False
            break

    # 올바른 경우
    if is_correct:
        return u + solution(v)

    # 올바르지 않은 경우
    temp = "(" + solution(v) + ")"
    reversed_u = ""
    for c in u[1:-1]:
        reversed_u += ")" if c == "(" else "("

    return temp + reversed_u