[Python 파이썬] 프로그래머스 - 괄호 변환 [2020 KAKAO BLIND RECRUITMENT]

 

2024년 6월 8일

문제 링크 : 프로그래머스 - 괄호 변환 [2020 KAKAO BLIND RECRUITMENT]

프로그래머스

 
 

---

문제 접근

 
카카오 다운 복잡한 구현 문제이다.
 
이런 문제는 알고리즘적 접근보다는, 문제를 정확히 이해하고 키워드를 뽑아낸 후 문제가 요하는 바를 빠짐 없이 체크해야 한다.
 

---

 

균형잡힌 괄호 문자열, 올바른 괄호 문자열

 
균형잡힌 괄호 문자열이란, 특정 괄호 문자열의 구성 요소 "(" 와 ")"의 개수가 일치하는 문자열을 뜻한다.
" (()) " , " ())( ", " )( " 모두 균형잡힌 괄호 문자열이다.
 
올바른 괄호 문자열이란, 괄호의 짝이 모두 맞는 문자열을 의미한다.
 
" (()) " 는 짝이 맞지만, " ())( ", " )( " 은 짝이 맞지 않기에, 균형잡힌 괄호 문자열이지만 올바른 괄호 문자열이 아니다.
 

---

 

문제가 목표하는 바

 
"(" 와 ")"로 이루어진 특정 문자열이 주어졌을 때, 이를 다음과 같은 로직으로 돌아가는 프로그램을 통해 올바른 순서대로 배치된 괄호 문자열을 알려주고자 한다.
 
프로그램 로직은 다음과 같다.
 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다.

 
 
우리는 이 로직을 그대로 코드로 옮기기만 하면 된다.
 
여기서 주의해야 할 점은 다음과 같다.
 

1. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리한다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 한다. v는 빈 문자열이 될 수 있다.
이는 w = (())))(( 일 때, u는 더 이상 분리할 수 없는 균형잡힌 문자열이어야 한다. w의 가장 왼쪽 괄호부터 비교해보았을 때, u = " (()) " , v = " )())(( "로 나누어야 한다는 의미이다. u = " (()) " 는  절대 균형잡힌 2개 이상의 다른 균형잡힌 문자열로 분리가 불가능하기 때문이다.


2. u가 올바른 괄호 문자열인 상황과 올바르지 못한 괄호 문자열인 상황을 구분하여 로직을 구성해야 한다.

3. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다는 의미는, 문자열 순서를 바꾼다는 의미가 아닌 ( => ) , ) => ( 의 이미이다. 즉 반대 괄호로 치환해주라는 의미이다.

4. u가 올바른 괄호 문자열이 아니라면 일어나는 로직 순서에 유의한다.
특히, 문자열 v에 대해 재귀적으로 수행한 결과가 solution(v)라면, 4-1 ~ 4-3은 다음과 같이 문자열이 조합된다.

"(" + solution(v) + ")"

 
초기 괄호 문자열이 주어지면, 맨 앞에서부터 탐색하며 u, v를 나누어주고 u가 어떤 괄호 문자열인지 판단하여 v를 적절히 재귀호출시켜 v에 대해 또 u, v를 나누어주고를 반복하는 분할-정복의 느낌으로 문제를 해결하면 된다.
 

---

전체 코드

 

# u가 올바르지 못한 괄호 문자열이면 양 옆 괄호를 삭제 후, 나머지 괄호들을 뒤집어야 함.
def u_isNotValid(_u):
    u = ""
    for i in range(1, len(_u) - 1):
        if _u[i] == "(":
            u += ")"
        else:
            u += "("

    return u


# 올바른 괄호 문자열인지 확인
def isValid(bracket):
    stack = []
    now_idx = 0
    while now_idx < len(bracket):
        now = bracket[now_idx]
        if now == "(":
            stack.append(now)
        else:
            # 스택에 아무것도 없는데 ) 로 시작하면 절대 올바를 수 없는 괄호
            if not stack:
                # 올바르지 않은 괄호 문자열
                return False
            # 스택에 뭔가 있다면 무조건 ( 일 것 -> stack.pop()
            else:
                stack.pop()
        now_idx += 1

    return True


def solution(p):
    answer = ""

    now_idx = 0
    length = len(p)

    bracket = []
    left = 0
    right = 0
    while now_idx < length:
        bracket.append(p[now_idx])
        if p[now_idx] == "(":
            left += 1
        else:
            right += 1

        if left == right:
            v = p[now_idx + 1:]
            if isValid(bracket):
                u = "".join(bracket)
                answer += u
                # u를 제외한 나머지 문자 v에 대해 재귀적으로 접근
                answer += solution(v)
            else:
                u = u_isNotValid(bracket)
                # 순서 1. (  + v에 대해 1단계부터 재귀적으로 수행한 결과 + ) 를 이어 붙임
                temp = "(" + solution(v) + ")"
                answer += temp
                # 순서 2. u를 이어 붙임
                answer += u
            break

        now_idx += 1

    return answer


if __name__ == "__main__":
    p = "()))((()"

    print(solution(p))

---

풀이 후기

 

 
이 화면 보려고 1시간이나 투자했다.. 실제 코딩테스트를 치르면 시간 안에 못 풀지 않았을까 싶었다.
 
코테는 돌고 돌아 구현/시뮬레이션 인 듯 싶다.
 
추가로, 2024년 카카오 인턴쉽 코딩테스트를 참가해 본 경험까지 생각해보니 카카오는 복잡한 구현 문제를 통해 응시생들의 독해력, 문제해결력, CS적 사고능력을 모두 확인해보고 싶어하는게 느껴졌다.
그 당시 1번 문제도 구현 문제였는데, 엄청 오래걸렸다 ㅠ