[Python] 프로그래머스 Lv_2 괄호 회전하기

Jihoon Oh·2021년 8월 23일
algorithmpython프로그래머스
0

프로그래머스 풀이

목록 보기
3/3

괄호 회전하기

문제 설명

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

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

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

제한사항

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

입출력 예

sresult
"{}"3
"}]()[{"2
"[)(]"0
"}}}"0

나의 풀이

아직 알고리즘 문제 풀이가 익숙하지 않은지라 처음에 문제를 딱 봤을때는 어떤 방식으로 풀어야 할 지 감이 안왔다. 생각해 보았을 때, 우선은 주어진 문자열이 올바른 괄호 문자열인지를 판별하는 것이 먼저라는 생각이 들었다.

올바른 괄호 문자열인지 판별하는 방법 자체는 의외로 간단하다고 생각했다. 괄호에는 여는 괄호( '(' , '[' , '{' ) 와 닫는 괄호( ')' , ']' , '}' )가 있는데, 닫는 괄호가 나왔을 때 앞에 나온 괄호들이 제대로 닫혀 있는지를 판단하면 된다고 생각했다.

이 과정을 for 문을 이용하여 주어진 문자열의 모든 문자에 대해서 판단을 하고, 모든 문자에 대해 테스트를 통과하면 answer 값을 1 올려주는 풀이를 생각했다. 그런데 아직 파이썬에 익숙하지 않은 탓인지, 테스트를 모두 통과했을 때 answer 값을 1 올려주는 것 보다 테스트를 통과하지 못했을 때 answer 값을 1씩 빼 주는 것이 낫겠다는 생각을 했다. (어차피 for ~ else 문을 사용하면 두 풀이에 큰 차이가 없는데 왜 그랬는지 잘 모르겠다.)

최종적으로 작성한 코드는 다음과 같다.

from collections import deque

def solution(s):
    answer = len(s)
    s = deque(s)
    bracket = {')': '(', ']': '[', '}': '{'}
    for _ in range(len(s)):
        characters = []
        for c in s:
            if c in bracket:
                if characters and characters[-1] == bracket[c]:
                    characters.pop()
                else:
                    answer -= 1
                    break
            else:
                characters.append(c)
        else:
            if characters:
                answer -= 1
        s.rotate(-1)
    return answer

회전을 0회전부터 len(s)-1회전까지 len(s)번 만큼 하기 때문에, answer의 최댓값은 모든 회전에서 올바른 괄호 문자열이 되는 len(s)다. 그리고 문자열로 제공된 s값은 풀이의 편의성을 위해 collections의 deque를 import 해서 덱으로 만들어주었다

딕셔너리를 사용했는데, 매 번 if 문으로 ')', ']', '}'를 판별하기가 귀찮았기 때문이다. 매 번 if 문을 사용하기 보다 그냥 딕셔너리에 key와 value로 여는 괄호와 닫는 괄호 쌍을 저장하면 편하게 찾을 수 있겠다는 생각이 들어서, 괄호들을 저장할 딕셔너리 bracket은 닫는 괄호들을 key로, 여는 괄호들을 value로 저장해 주었다.

회전을 0회전부터 len(s)-1 회전까지 하기 때문에 매 회전마다 올바른 괄호 문자열을 판별하기 위한 len(s) 범위의 for문을 작성했다. 이 때 for의 인덱스를 사용할 필요가 없으므로 _로 대체해 주었다.

    for _ in range(len(s)):
        characters = []

for 문의 맨 처음 시작때는 characters 라는 리스트를 초기화 해 주었는데, 일종의 스택으로 사용하기 위한 리스트로 만들어주었다. 이 characters 리스트 안에는 문자열을 순회하면서 나오는 문자들을 저장해 줄 것이다. 그 후 다시 for 문을 작성해 주었는데, 해당 for 문은 문자열의 모든 문자들을 순회하면서 올바른 괄호 문자열인지 판별해주는 for 문으로 작성했다.

        for c in s:
            if c in bracket:
                if characters and characters[-1] == bracket[c]:
                    characters.pop()
                else:
                    answer -= 1
                    break
            else:
                characters.append(c)
        else:
            if characters:
                answer -= 1
        s.rotate(-1)

우선 순회하는 문자 c가 bracket에 들어있는지, 즉 닫는 괄호인지를 판단한다. 전술했듯이, 올바른 괄호 문자열인지는 여는 괄호보다 닫는 괄호를 기준으로 판정해야 하기 때문이다. 처음에는 if bracket[c] in characters: 로 characters 리스트 안에 닫는 괄호에 알맞게 해당하는 여는 괄호가 들어있는지를 기준으로 판정을 하고, 들어 있으면 그 값을 remove 해주고 들어있지 않으면 answer 값을 하나 줄여준 뒤 break로 빠져나갔었다.

그런데 이렇게 할 경우 14번 케이스가 실패했는데, 생각해보니 "({)" 같은 케이스, 즉 정상적으로 열고 닫는 괄호 안에 여는 괄호만 존재하는 케이스를 잡아낼 수 없었다.

그래서 생각을 다시 해 보았는데, 생각해보니 너무나도 간단한 문제였다. 올바른 괄호 문자열이려면 반드시 괄호들로 둘러쌓인 맨 안쪽은 같은 짝의 괄호들로 이루어져야 한다는 사실을 망각하고 있던 것이었다! 즉 순서대로 진행한다고 생각했을 때, 리스트의 맨 바깥쪽, 스택으로 치자면 top 값이 현재의 닫는 괄호 값과 짝을 이루면 통과하고, 만약 짝을 이루지 않는다면 올바른 괄호 문자열일 수가 없으니 for 문을 탈출하면 되는 것이었다. 이 때, characters 리스트의 -1번째 인덱스로 접근해야 하므로 빈 리스트가 아니라는 조건을 함께 넣어 주었다. (이 조건을 넣지 않을 경우 빈 리스트에서 조건문을 체크할 시 런타임 에러가 발생한다.)

따라서 if characters and characters[-1] == bracket[c]: 가 조건이 되고, 이 조건이 만족하면 characters 리스트에서 pop()으로 짝이 맞는 맨 바깥쪽 괄호를 제거해주었다.

만약 c가 bracket에 없다면(딕셔너리에 in을 사용하면 key 값을 기준으로 찾는다) 여는 괄호이므로 characters에 append 해준다.

for문을 모두 통과하면 마지막으로 한가지 조건을 더 판단해주어야 하는데, 바로 characters에 문자가 남아 있는지 여부다. 이는 '((({}'나 '(({}(' 같이 완전한 괄호들이 제거된 이후에 왼쪽 괄호들만 남아있는(오른쪽 괄호만 있는 경우는 이미 앞선 조건문들에서 걸러지므로) 경우를 체크한다. 이 때, 이미 앞선 for 문에서 answer 값이 감소된 경우에 중복해서 체크하지 않도록 for ~ else 문을 사용해 주었다.

이 과정이 각 회전 당 올바른 괄호 문자열 판별이므로, 뒤에 deque의 rotate기능을 사용해서 s.rotate(-1)로 왼쪽으로 1회전 시켜주고 맨 바깥쪽 for 문의 다음 순회로 넘어가도록 했다.

채점 결과

테스트 1 〉	통과 (5.34ms, 10.2MB)
테스트 2 〉	통과 (2.91ms, 10.3MB)
테스트 3 〉	통과 (3.00ms, 10.3MB)
테스트 4 〉	통과 (4.08ms, 10.2MB)
테스트 5 〉	통과 (15.65ms, 10.1MB)
테스트 6 〉	통과 (6.13ms, 10.3MB)
테스트 7 〉	통과 (8.16ms, 10.4MB)
테스트 8 〉	통과 (11.04ms, 10.2MB)
테스트 9 〉	통과 (24.42ms, 10.3MB)
테스트 10 〉	통과 (35.36ms, 10.1MB)
테스트 11 〉	통과 (53.89ms, 10.2MB)
테스트 12 〉	통과 (0.01ms, 10.1MB)
테스트 13 〉	통과 (0.01ms, 10.1MB)
테스트 14 〉	통과 (0.01ms, 10.2MB)
profile
Jihoon Oh
Backend Developeer
이전 포스트

[Python] 프로그래머스 Lv_2 프린터

0개의 댓글