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

---

Stack을 이용한다면 쉽게 풀 수 있는 문제였습니다. Stack에 대해서는 추가적으로 내용을 모아서 조만간에 글을 올리겠습니다. 한번쯤 제대로 정리하고 싶었던 부분이기도 했구요!

문제

괄호 회전하기 링크

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

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

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

제한사항

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

입출력 예

내 풀이

이 문제가 나타내는 바를 그대로 조건문으로 걸어서 실행하면 시간 초과로 코드 답안이 나오지 못하는 부분이 발생했습니다. 따라서, 조건문 전에 올바르지 않은 괄호 문자열을 먼저 찾고 거르려고 했습니다. 예를 들어, 문자열의 개수가 홀수이거나 특정 괄호의 여는 괄호와 닫는 괄호의 개수가 다를 경우, 올바른 괄호 문자열이 나오지 않기 때문에 return 0을 걸어주었습니다. 이 다음에 괄호 개수만큼, for문을 걸어주고, 만들어진 괄호 문자열을 차례대로 하나하나 보기 위해 for문을 한번 더 걸어주었습니다. 이 때, 특정 괄호에 대하여 여는 괄호보다 닫는 괄호가 많을 경우 올바르지 않은 괄호 문자열로 취급하였고, 지금까지 언급했던 모든 부분을 통과했을 시 올바른 괄호 문자열로 확정했습니다.

from collections import Counter

def solution(s) :
    answer = 0
    num = len(s)

    if len(s) % 2 == 1 :     # s 개수가 홀수면 0
      return 0

    ss = Counter(s)     # 어느 하나의 괄호라도 여는 괄호와 닫는 괄호의 개수가 서로 다르면 0
    if (ss['['] != ss[']']) or (ss['{'] != ss['}']) or (ss['('] != ss[')']) :
      return 0

    for _ in range(num) :
      s2 = s[1 :] + s[0]     # 앞의 괄호를 제일 뒤로 보냄
      temp = ''
      temp3 = True
      
      for i in range(num) :
        temp += s2[i]     # for문을 통해 앞의 문자부터 차례대로 1개씩 넣으면서 아래 내용 확인
        temp2 = Counter(temp)

        if (i < (num - 1)) :     # 여는 괄호와 닫는 괄호가 서로 다른 괄호면 False로 놓고 break
        
          if (s2[i] == '[') and (s2[i + 1] in ['}', ')']) :
            temp3 = False
            break
            
          if (s2[i] == '{') and (s2[i + 1] in [']', ')']) :
            temp3 = False
            break
            
          if (s2[i] == '(') and (s2[i + 1] in [']', '}']) :
            temp3 = False
            break
            
        # 여는 괄호보다 닫는 괄호가 더 많으면 False
        if (temp2['['] < temp2[']']) or (temp2['{'] < temp2['}']) or (temp2['('] < temp2[')']) :
          temp3 = False
          break
          
      if temp3 == True :     # 위의 False 조건을 모두 만족하지 않으면 통과
        answer += 1
       
      s = s2

    return answer

다른 사람들의 풀이

Stack을 이용한 좋은 풀이를 소개합니다. Stack의 가장 큰 특징 중 하나는 후입선출이라는 점입니다. 즉, 나중에 들어온 원소가 먼저 나가는 구조를 말합니다. 처음에 코드는 빈 리스트인 Stack을 정의합니다. 첫 번째 원소를 Stack으로 들인다음, 두 번째 원소부터 비교를 시작하여 여는 괄호 바로 다음으로 닫는 괄호가 올시, pop()을 이용하여 여는 괄호와 닫는 괄호를 Stack에서 추출해 버립니다. 이런 식으로 끝까지 진행했을 때, Stack에 남아있는 원소가 없을 시 True, 남아있는 원소가 있다면 False가 도출됩니다. 이뿐 아니라 함수 두 개를 따로 정의하여 편리함도 높인 코드라고 말할 수 있습니다. 이런 후입선출의 특징을 가진 Stack을 이용하여 다양한 코딩 문제를 쉽게 해결할 수 있습니다. Stack 활용성을 높일 수 있도록 연습을 더 해야겠어요! 😁

def is_valid(s):
    stack = []
    for ch in s:
        if not stack:
            stack.append(ch)
        elif stack[-1] == '(':
            if ch==')': stack.pop()
            else: stack.append(ch)
        elif stack[-1] == '{':
            if ch=='}': stack.pop()
            else: stack.append(ch)
        elif stack[-1] == '[':
            if ch==']': stack.pop()
            else: stack.append(ch)

    return False if stack else True

def solution(s):
    answer = 0
    for i in range(len(s)):
        answer += is_valid(s[i:]+s[:i])
    return answer