문제
https://school.programmers.co.kr/learn/courses/30/lessons/76502
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입출력

해설
해당 문제는 전에 풀이했던 올바른 괄호의 확장판 느낌의 문제이다.
이번에는 들어올 수 있는 괄호 문자가 총 3가지로 다음과 같다.
"{}", "()", "[]"
그렇기 때문에 if문을 통해서 구현해도 좋지만 해시맵을 이용해서 풀이를 진행하면 깔끔하게 구현할 수 있기 때문에
해시맵을 사용하였다.
괄호를 회전하는 것은 방법이 여러가지가 있을 수 있지만 필자는 deque를 이용하여 O(1)에 회전하는 방식을 구현하였다.
파이썬에는 rotate라는 함수를 통하여 pop_front, push_back의 느낌을 낼 수가 있다.
그리하여 회전을 하면서 올바른 괄호 쌍인지 판단내렸다.
정답코드
더보기
'''
'25. 08. 24
1. 올바르게 짝지어진 괄호
2. 1 <= |S| <= 1000일 때
S의 값을 왼쪽으로 쉬프트 했을 때 올바르게 짝지어진 괄호 문자열이 되게 하는 x의 개수를 return하여라.
ex)
()[]{} x = 0 만족
x는 0부터 5까지만 가능, 0일 때만 만족한다. 아니지
[]{}() x = 2,
{}()[] x = 4 총 3번 가능
1. 왼쪽으로 쉬프트 하는 방식 O(1)에 가능
2. 올바른 괄호인지 판단하는 방법 O(|S|)에 판단 가능
3. 총 왼쪽으로 쉬프트하는 횟수 |S| - 1번
쉬프트 하면서 올바른 괄호 판단하는 시간 복잡도 => O(|S|^2) 10^6 이므로 충분히 N^2으로 돌려도 됨.
'''
from collections import deque
def is_right(word: deque) -> bool:
s = []
other = {']' : '[', '}' : '{', ')' : '('}
for ch in word:
if ch in '[({':
s.append(ch)
#빼내야 함.
else:
#스택의 맨 위가 쌍을 이루는 괄호인지 판별
if s and s[-1] == other[ch]:
s.pop()
#아니면 끝내기
else:
return False
if s:return False
return True
def solution(s):
answer = 0
dq = deque([*s])#디큐에 넣어 놓는다.
#쉬프트 횟수는 deque_len번 => 변경 후 체크할 거기 때문에
for _ in range(len(dq)):
dq.rotate(-1)
answer += is_right(dq)
return answer
깃허브 : https://buly.kr/8TrDAid
'코딩테스트 > programmers' 카테고리의 다른 글
| 프로그래머스 / 정렬, 이분탐색 / H-Index (0) | 2025.08.31 |
|---|---|
| 프로그래머스 / 구현 / n^2 배열 자르기 (0) | 2025.08.30 |
| 프로그래머스 / 슬라이딩 윈도우 / 할인 행사 (0) | 2025.08.24 |
| 프로그래머스 / 슬라이딩 윈도우 / 연속 부분 수열 합의 개수 (0) | 2025.08.24 |
| 프로그래머스 / 수학 / 예상 대진표 (0) | 2025.08.24 |