99클럽 코테 스터디 28일차 TIL + 스택/큐

오늘의 문제 - 스택/큐

프로그래머스 - 괄호 회전하기

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

---

풀이 및 접근 방식

스택/큐 이용 풀이

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

        
    return answer
    
 # 출처: https://velog.io/@znsxre/프로그래머스-괄호-회전하기-파이썬

 

풀이

1. 초기화:
   •  s를 리스트로 변환하여 회전 가능하게 만든다.
   •  answer 변수는 0으로 괄호 문자열이 되는 경우의 수를 카운트한다.
2. 회전:
   •  문자열의 길이만큼 반복하여, s를 회전시키며 각각의 회전된 문자열에 대해 괄호가 올바른지 확인한다.
   •  문자열을 한 칸씩 회전시키기 위해 s.append(s.pop(0))를 사용한다. 이는 첫번째 문자를 마지막에 추가하는 것이다.
3. 괄호 유효성 검사:
   
   •  문자열의 각 문자에 대해 만약 stack이 비어 있지 않고, stack의 마지막 요소와 현재 문자가 짝을 이루는 괄호라면 stack에서 마지막 요소를 제거한다. 그렇지 않으면 현재 문자를 stack에 추가한다.
   •  문자열의 모든 문자를 검사한 후, stack이 비어 있으면 해당 회전된 문자열이 올바른 괄호 문자열이므로 answer를 1 증가시킨다.
4. 결과 반환:
   •  모든 회전된 문자열을 검사한 후, answer를 반환한다.

시간 복잡도

• 문자열의 길이를 n이라고 할 때, 외부의 for 루프는 n번 반복한다.
• 각 회전된 문자열에 대해 내부의 for 루프가 다시 n번 반복되며, 여기서 stack의 pop과 append 작업이 발생한다. 이 작업은 평균적으로 O(1)입니다.

따라서, 전체 시간 복잡도는 O(n * n)이 된다.

리스트 슬라이싱 이용 풀이

def is_valid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    
    return not stack

def solution(s):
    if len(s) % 2 != 0:
        return 0
    
    answer = 0
    for i in range(len(s)):
        if is_valid(s):
            answer += 1
        s = s[1:] + s[0]  # 문자열 회전
    
    return answer

 

풀이

1. is_valid 함수:
   •  이 함수는 주어진 문자열 s가 올바른 괄호 문자열인지 확인한다.
   •  stack을 사용하여 각 괄호를 검사하며, 닫는 괄호가 나왔을 때 stack의 최상위 원소와 짝이 맞는지 확인한다.
   •  짝이 맞지 않으면 False를 반환하고, 모든 문자를 검사한 후 스택이 비어있으면 True를 반환한다.
2. solution 함수:
   •  먼저 문자열의 길이가 홀수라면 절대 올바른 괄호 문자열이 될 수 없으므로 0을 반환한다.
   •  문자열을 한 칸씩 회전시키면서 is_valid 함수를 호출해 유효성을 확인한다.
   •  유효한 문자열이 발견되면 answer를 1씩 증가시킨다.
   •  마지막으로 유효한 문자열의 개수를 반환한다.

---

회고

괄호 관련 문제는 항상 스택/큐와 연관된 문제로 나오는 것 같다. 코딩테스트 문제에서도 많이 출제되었던 것 같아서 꼭 익혀두면 좋을 것 같다.