[프로그래머스] Level 2_괄호 회전하기(월간 코드 챌린지 시즌2)

📌문제 유형

월간 코드 챌린지 시즌2

 

📌문제

프로그래머스

 

📌나의 문제풀이

1차 시도(85.7)

 - [, (, {가 들어오면 +1, ],},)가 들어오면 -1

 - 문자열 개수만큼 반복하기

from collections import deque

def correct(s):
    cnt_1, cnt_2, cnt_3 = 0, 0, 0
    if s[0] not in ['[','{','(']:
        return 0
    
    # 중간에 틀어지는 애들 고민하기
    for i in range(len(s)):
        if s[i] =='[':
            cnt_1 += 1
        elif s[i] ==']':
            cnt_1 -= 1
            if cnt_1 < 0:
                return 0
            
        if s[i] == '(':
            cnt_2 += 1
        elif s[i] == ')':
            cnt_2 -= 1
            if cnt_2 < 0:
                return 0
            
        if s[i] == '{':
            cnt_3 += 1
        elif s[i] == '}':
            cnt_3 -= 1
            if cnt_3 < 0:
                return 0  
    return 1
            
def solution(s):
    answer = 0
    s = deque(s)
        
    answer += correct(s)    
    for i in range(1,len(s)):
        first = s.popleft()
        s.append(first)
        answer += correct(s)
        
    return answer

2차 시도(92.9)

 - 1차 시도에서 cnt의 개수가 0이 아닐 경우, 0을 리턴하는 것만 추가

from collections import deque

def correct(s):
    cnt_1, cnt_2, cnt_3 = 0, 0, 0
    
    if s[0] in [']','}',')']:
        return 0
    
    # 중간에 틀어지는 애들 고민하기
    for i in range(len(s)):
        if s[i] =='[':
            cnt_1 += 1
        elif s[i] ==']':
            cnt_1 -= 1
            if cnt_1 < 0:
                return 0
            
        if s[i] == '(':
            cnt_2 += 1
        elif s[i] == ')':
            cnt_2 -= 1
            if cnt_2 < 0:
                return 0
            
        if s[i] == '{':
            cnt_3 += 1
        elif s[i] == '}':
            cnt_3 -= 1
            if cnt_3 < 0:
                return 0
    # 추가        
    if cnt_1 != 0 or cnt_2 != 0 or cnt_3 != 0:
        return 0
    
    return 1
            
def solution(s):
    answer = 0
    s = deque(s)
        
    answer += correct(s)    
    for _ in range(1,len(s)):
        first = s.popleft()
        s.append(first)
        answer += correct(s)
        
    return answer

3차 시도(통과)

- 테케 14번만 통과 못함 (14번 예시, ([{)}] 일 때, 답 0)

- stack 이용

• stack에 {,[,( 문자만 넣기
• stack 맨 끝과 ],},) 가 연결되는 경우 stack.pop()
• stack이 비어있을 경우 0, 아니면 1

from collections import deque

def correct(s):
    stack = list()
    
    if s[0] in ['}',']',')']:
        return 0
    
    for i in s:
        if i in ['{','[','(']:
            stack.append(i)
        else:
            if i in  ['}',']',')'] and len(stack) == 0:
                return 0
            
            if i == '}' and stack[-1] == '{':
                stack.pop()
            elif i == ']' and stack[-1] == '[':
                stack.pop()
            elif i == ')' and stack[-1] == '(':
                stack.pop()
            else:
                return 0
                
    if len(stack) == 0:
        return 1
    else:
        return 0
                
            
def solution(s):
    answer = 0
    s = deque(s)
        
    answer += correct(s)    
    for _ in range(1,len(s)):
        first = s.popleft()
        s.append(first)
        answer += correct(s)
        
    return answer

 

📌다른 사람의 문제풀이

1) 유사 풀이

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

 

📌리뷰

 - 스택(stack) : 후입후출. 나중에 들어온게 제일 먼저 나간다. 짝 맞추기 할 때 유용

• 리스트로 stack 만들기

[Python] Stack 사용하기