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

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

프로그래머스

 

풀이 :

첫번째 방법에서 시간 효율이 떨어지는 것 같아 더 좋은 방법을 모색해보았음

 

첫번째 방법 

1. 문자열 개수가 홀수일 경우와 짝수일 경우로 나누었음(문자열 개수가 홀수일 경우 무조건 올바른 문자열이 아니므로)

2. 반복문을 통해 문자열의 개수만큼 회전을 시키고 각 케이스마다 올바른 문자열인지 판별

3. while문 안의 반복문을 통해 인덱스를 1번부터 시작하여 올바른 문자열인지 판별(chk 변수를 통해 while문 제어)

Ex)

stack_copy[k] == ')' 

stack_copy[k-1] == '('

일 경우 두 원소는 올바른 문자열이므로 stack_copy에서 삭제

4. for k in range(1,len(stack_copy)) 반목문을 마쳤을때 chk == Fasle 일 경우 올바른 문자열이 아닌 경우가 존재하는 것이므로 while문 탈출

5. stack_copy의 크기가 0이면 answer += 1

 

두번째 방법

1. 문자열 회전 시키는 부분까지는 위의 방법과 동일.

2. stack_temp라는 임시 stack을 하나 생성(열린 괄호를 담기 위함)

3. 문자열의 개수만큼 반복문을 돌면서 열린괄호일 경우 stack_temp에 추가

4. 닫힌 괄호일 경우 stack_temp[-1](가장 위에 있는 원소)가 해당 닫힌괄호와 짝을 이루는 열린 괄호일경우 stack_temp.pop()을 통해 가장 위 원소 삭제, 그렇지 않을 경우 chk = False 후 반복문 탈출

5. chk == True이고 stack_temp == 0일 경우 answer += 1

 

 

* Tip - 만약 마지막 테스트 케이스가 실패할 경우 '[ ( ] )' 의 경우를 생각해 보기 바람

 

코드 :

1. 첫번째 방법

from collections import deque
import copy

def solution(s):
    answer = 0
    stack = deque(s)
    rotate = 0       # 회전 수

    if len(s) % 2 != 0:      # 문자열 개수가 홀수 일때
        answer = 0
    else:                    # 문자열 개수가 짝수 일때
        for _ in range(len(s)):    # 문자열 개수만큼 회전
            stack_copy = copy.deepcopy(stack)
            for _ in range(rotate):
                stack_copy.append(stack_copy[0])
                stack_copy.popleft()
            
            rotate += 1
            chk = False   # 여는 괄호와 닫힌 괄호가 짝을 이루면 chk = True, 짝을 이루지 않으면 chk = False
        
            while stack_copy:   
                chk = False
                for k in range(1,len(stack_copy)):
                    if stack_copy[k] == ')' and stack_copy[k-1] == '(':
                        del stack_copy[k]       
                        del stack_copy[k-1]
                        chk = True
                        break
                    if stack_copy[k] == '}' and stack_copy[k-1] == '{':
                        del stack_copy[k]
                        del stack_copy[k-1]
                        chk = True
                        break
                    if stack_copy[k] == ']' and stack_copy[k-1] == '[':
                        del stack_copy[k]
                        del stack_copy[k-1]
                        chk = True
                        break
                if chk == False:   # 괄호가 짝을 이루지 않아서 for문을 이탈하게 되면 while문 종료 
                    break
            if len(stack_copy) == 0:  # stack_copy 개수가 0이면 올바른 괄호 문자열 이므로
                answer += 1
    return answer

2. 두번째 방법

from collections import deque
import copy

def solution(s):
    answer = 0
    stack = deque(s)
    rotate = 0          # 회전 수

    for _ in range(len(s)):    # 문자열 개수만큼 회전
        stack_copy = copy.deepcopy(stack)
        for _ in range(rotate):
            stack_copy.append(stack_copy[0])
            stack_copy.popleft()
        
        rotate += 1     # 회전 수 1 증가
        
        stack_temp = deque()     # 열린 괄호 '(', '{', '[' 를 담을 stack 생성        
        chk = True                  
        for i in range(len(s)):
            # 열린 괄호일 경우 stack_temp에 추가
            if stack_copy[i] == '(' or stack_copy[i] == '{' or stack_copy[i] == '[':   
                stack_temp.append(stack_copy[i])
            # 닫힌 괄호 ')' 일경우
            elif stack_copy[i] == ')':          
# stack_temp에 열린 괄호o, stack_temp의 마지막 원소가 '('일 경우 stack_temp 마지막 원소 pop
                if len(stack_temp) != 0 and stack_temp[-1] == '(':   
                    stack_temp.pop()
# stack_temp에 열린 괄호x, stack_temp의 크기가 0이 아니고 열린 괄호가 '('가 아닐 경우 반복문 탈출
                else:  
                    chk = False
                    break
            elif stack_copy[i] == '}':
                if len(stack_temp) != 0 and stack_temp[-1] == '{':
                    stack_temp.pop()
                else:
                    chk = False
                    break
            elif stack_copy[i] == ']':
                if len(stack_temp) != 0 and stack_temp[-1] == '[':
                    stack_temp.pop()
                else:
                    chk = False
                    break
        # chk == True이고 stack_temp의 크기가 0일 경우 전부 올바른 문자열이므로 answer += 1
        if chk == True and len(stack_temp) == 0:   
            answer += 1
    return answer