프로그래머스 76502번 문제인 "괄호 회전하기" Lv.2을 파이썬으로 풀어보도록 하겠습니다.
[프로그래머스] 괄호 회전하기 Lv.2 - [파이썬/python]
💻 문제 설명
다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
(),[],{}는 모두 올바른 괄호 문자열입니다.- 만약
A가 올바른 괄호 문자열이라면,(A),[A],{A}도 올바른 괄호 문자열입니다. 예를 들어,[]가 올바른 괄호 문자열이므로,([])도 올바른 괄호 문자열입니다. - 만약
A,B가 올바른 괄호 문자열이라면,AB도 올바른 괄호 문자열입니다. 예를 들어,{}와([])가 올바른 괄호 문자열이므로,{}([])도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 반환(return) 하도록 solution 함수를 완성해주세요.
🚨 제한사항
s의 길이는 1 이상 1,000 이하입니다.
!!!정답 주의!!!
🌟 소스 코드
def solution(s):
count = 0 # 올바른 괄호 문자열이 되는 회전 횟수를 저장할 변수
s_pairs = { # 괄호 쌍을 나타내는 딕셔너리
')': '(',
']': '[',
'}': '{'
}
for i in range(len(s)):
stack = [] # 스택을 초기화하여 현재 회전에 대한 괄호를 저장할 변수
rotated = s[i:] + s[:i] # 문자열을 i칸 왼쪽으로 회전
for b in rotated: # 회전된 문자열의 각 문자에 대해 순회
if b in ')]}': # 문자열에서 닫힌 괄호를 만난 경우
# 스택이 비어 있지 않고, 짝이 맞는 여는 괄호가 맨 위에 있는 경우
if stack and (stack[-1] == s_pairs[b]):
stack.pop() # 짝이 맞는 열린 괄호를 스택에서 제거
continue # 현재 괄호를 처리하고 다음 괄호로 진행
else: # 스택이 비어 있거나 짝이 맞지 않는 경우
break # 올바르지 않은 괄호 문자열이므로 반복 종료
stack.append(b) # 여는 괄호일 경우, 스택에 추가
else: # 'for' 반복문이 'break' 없이 정상적으로 종료된 경우
if not stack: # 스택이 비어 있는 경우 (모든 괄호가 짝을 이룬 경우)
count += 1
return count
⏱ 시간복잡도
위 코드의 시간복잡도는 O(n^2)입니다.
외부 루프 (i에 대한 루프): for i in range(len(s))
외부 루프 (i에 대한 루프) 시간복잡도: O(n), 여기서 n은 입력 문자열 s의 길이입니다.
내부 루프 (b에 대한 루프): for b in rotated
내부 루프 (b에 대한 루프) 시간복잡도: O(n), 회전된 문자열 rotated의 길이도 최대 n입니다.
내부 루프가 외부 루프 안에 중첩되어 있으므로, 전체 시간복잡도는 외부 루프와 내부 루프의 시간복잡도를 곱한 것과 같습니다.
따라서 전체 시간복잡도는 O(n) * O(n) = O(n^2)입니다. 이 코드는 입력 문자열 길이의 제곱에 비례하는 시간복잡도를 갖습니다.
🏳🌈 테스트 결과
728x90
'코딩테스트' 카테고리의 다른 글
| [프로그래머스] 과제 진행하기 - Lv.2 (42) | 2023.11.02 |
|---|---|
| [프로그래머스] 구명보트 - Lv.2 (49) | 2023.11.01 |
| [프로그래머스] 영어 끝말잇기 - Lv.2 (53) | 2023.10.29 |
| [프로그래머스] 피보나치 수 - Lv.2 (57) | 2023.10.28 |
| [프로그래머스] 짝지어 제거하기 - Lv.2 (55) | 2023.10.27 |