[프로그래머스/Lv.2] 괄호 회전하기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/76502

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

(), [], {} 는 모두 올바른 괄호 문자열입니다.
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

s의 길이는 1 이상 1,000 이하입니다.

입출력 예

입출력 예 #1

다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

나의 풀이

def solution(s):
    close = [")", "}", "]"]
    whole = ["()", "{}", "[]"]
    answer = 0
    
    for i in range(len(s)):
    	# 닫는 괄호로 시작하면 유효할 수 없으므로 패스함
        if s[i] in close:
            continue
        
        stack = [s[i]]
        for j in range(1, len(s)):
            k = (i+j) % len(s)
            
            if s[k] in close and stack:
                if stack[-1] + s[k] == whole[close.index(s[k])]:
                    stack.pop()
            else:
                stack.append(s[k])
            
        if not stack:
            answer += 1
            
    return answer

접근 방식

기본적으로 회전된 문자열마다 올바른 괄호 문자열인지를 검사하는 방식으로 접근했다.

이 과정에서 두 가지 문제를 해결해야 했다.

1. 문자열을 어떻게 회전할 것인가

2. 문자열이 올바른 괄호로 이루어져 있는지를 어떻게 판단할 것인가

문자열 회전

바깥쪽 for문에서 시작 인덱스 `i`를 기준으로 회전된 문자열을 생성한다.

회전된 문자열의 인덱스는 다음과 같이 계산할 수 있다.

`k = (i+j) % len(s)`

이 방법 외에도

`deque.rotate(-1)`로 문자열을 간단하게 회전하거나

`s[i:] + s[: i]` 문자열을 슬라이스한 뒤 붙여서 사용할 수도 있다.

올바른 괄호 검사

if s[i] in close:
    continue

문자열이 닫는 괄호로 시작하는 경우는 올바른 괄호가 될 수 없으므로,

처음부터 `continue`로 건너뛴다.

stack = [s[i]]
for j in range(1, len(s)):
    k = (i+j) % len(s)

    if s[k] in close and stack:
        if stack[-1] + s[k] == whole[close.index(s[k])]:
            stack.pop()
    else:
        stack.append(s[k])

회전된 문자열을 순회하면서 스택으로 괄호를 검사한다.

여는 괄호가 나오면 스택에 추가한다.

닫는 괄호가 나오면 스택의 마지막 값과 쌍을 이루는지 확인하고, 맞으면 `pop()` 한다.

예를 들어, `stack[-1] = '('`, `s[k] = ')'`이면 `'()'`가 되므로 `pop()`한다.

최종적으로 모든 괄호가 짝이 맞아서 스택이 비었다면

올바른 괄호 문자열이므로 카운트한다.

다른 사람의 풀이

from collections import deque

def check(s):
    while True:
        if "()" in s:
            s = s.replace("()", "")
        elif "{}" in s:
            s = s.replace("{}", "")
        elif "[]" in s:
            s = s.replace("[]", "")
        else:
            if s:
                return False
            else:
                return True

def solution(s):
    answer = 0
    queue = deque(s)
    
    for i in range(len(s)):
        if check("".join(queue)):
            answer += 1
        queue.rotate(-1)
            
    return answer

한 쌍의 괄호를 계속 공백으로 바꿔나가는 과정을 계속 해서

만약 최종적으로 문자열이 공백이 된다면 올바른 괄호 문자열로 판단한다.

회고

다른 사람들 풀이를 보니 나는 꽤나 창의적인(?) 방법으로 푼 거 같다. 나름 머리 많이 굴렸음...

저작자표시 (새창열림)

[프로그래머스/Lv.2] 괄호 회전하기 | 파이썬 Python

문제