프로그래머스 76502 괄호 회전하기

괄호 회전하기 문제에 대한 설명은 다음 링크를 참고해주시기 바랍니다. 문제 설명

프로그래머스

괄호 회전하기 문제는 주어진 문자열 s를 한 문자씩 회전한 결과들 중에 올바른 괄호를 가진 개수를 구하는 문제입니다. 따라서 문자열 s를 사용하여 나올 수 있는 모든 경우의 수를 탐색하는 완전 탐색 문제입니다.

 

따라서 문제를 해결하기 위한 순서는 다음과 같습니다.

1. 올바른 괄호를 만들 수 있는 문자열인지 확인한다.
2. 1의 결과가 참이라면 문자열 s를 순환하며 가능한 후보군을 배열에 저장한다. 거짓이라면 0을 반환한다.
3. 후보군을 순환하며 조건에 맞는 후보군만 올바른 괄호인지 판별한다.

더 자세한 설명을 위해 1번과 3번에 사용된 조건에 대해서 알아보겠습니다.

 

우선, 1번에 사용된 조건은 가능한 괄호 3종류의 닫힌 괄호와 열린 괄호의 개수를 비교하는 조건입니다. 만약 열린 괄호와 닫힌 괄호의 개수가 같지 않다면 모든 경우에 대해서 올바른 괄호를 만들 수 없다는 것이 보장되기 때문에 0을 반환하게 됩니다.

 

3번에 사용된 조건의 경우 후보군의 첫 번째 문자열이 닫힌 괄호라면 올바른 괄호를 만들 수 없다는 것이 보장되기 때문에 continue를 사용하여 바로 다음 후보군을 탐색하게 됩니다.

 

올바른 괄호를 판별하는 알고리즘은 스택을 사용하여 개발하였습니다. 올바른 괄호 판별 순서는 다음과 같습니다.

1. 현재 문자가 열린 괄호라면 스택에 넣어준다.
2. 현재 문자가 닫힌 괄호라면 스택의 값을 pop해준다. 이때, 스택이 비어있다면 거짓을 반환한다.
3. 가능한 괄호 3종을 순환하며 2의 결과와 같은 열린 괄호를 찾는다. 이때 닫힌 괄호가 현재 문자와 같지 않다면 거짓을 반환한다.
4. 모든 문자를 순환한 후에 스택에 값이 있다면 거짓을 반환한다. 반대의 경우 참을 반환한다.

앞서 설명한 모든 과정을 코드로 구현하면 다음과 같습니다.

def solution(s):
    answer = 0
    bracket = [('(', ')'), ('{', '}'), ('[', ']')]
    if not is_available_bracket(s, bracket):
        return 0
    else:
        for candidate in get_candidate_list(s):
            for _, close in bracket:
                if candidate[0] == close:
                    continue
            if is_right_bracket_pattern(candidate, bracket):
                print("".join(candidate))
                answer += 1
    return answer


def is_available_bracket(s, bracket):
    for open, close in bracket:
        if not is_open_and_close_bracket_count_equal(s, open, close):
            return False
    return True


def is_open_and_close_bracket_count_equal(s, open, close):
    return s.count(open) == s.count(close)


def get_candidate_list(s):
    candidate, candidate_list = list(s), []
    for char in s:
        candidate.pop(0)
        candidate.append(char)
        candidate_list.append(candidate[:])
    return candidate_list


def is_right_bracket_pattern(candidate, bracket):
    stack = []
    for item in candidate:
        for open, close in bracket:
            if item == open:
                stack.append(open)
            if item == close:
                if not stack: return False
                pop = stack.pop()
                for open, close in bracket:
                    if pop == open and item != close: return False
    return False if stack else True

함수들의 이름을 직관적으로 보이려고 신경을 썻지면 각 함수들에 대한 역할을 간단하게 설명하면 다음과 같습니다.

• is_available_bracket: 가능한 괄호를 순환하며 is_open_and_close_bracket_count_equal를 실행한다.
• is_open_and_close_bracket_count_equal: 주어진 문자열의 열린, 닫힌 괄호의 개수를 세어 같은지 비교한다.
• get_candidate_list: 주어진 문자열 s를 순환하며 가능한 경우를 배열에 저장하여 반환한다.
• is_right_bracket_pattern: 주어진 후보와 괄호를 사용하여 올바른 괄호인지 판별한다.

해당 문제는 3종류의 괄호에 대해서 올바른 괄호인지 판별하는 문제로 올바른 괄호의 활용입니다. 괄호 회전하기 풀이에 대해서 어려움이 있었다면 해당 문제를 풀어보시는 것을 추천드립니다.