문제 요약
소괄호, 대괄호, 중괄호로 이루어진 문자열 s가 주어진다.
문자열을 왼쪽으로 x칸 회전한 결과가 올바른 괄호 문자열이 되는 x의 개수를 구해야 한다.
왼쪽으로 1칸 회전
abcde -> bcdea올바른 괄호 문자열은 괄호의 개수뿐 아니라 열고 닫는 순서와 종류도 모두 맞아야 한다.
올바른 예: ()[]{}
올바른 예: {([])}
올바르지 않은 예: ([)]
올바르지 않은 예: (]핵심 아이디어
회전한 문자열이 올바른 괄호 문자열인지 확인할 때 스택을 사용한다.
여는 괄호를 만나면 스택에 넣고, 닫는 괄호를 만나면 스택의 마지막 괄호가 짝이 맞는 여는 괄호인지 확인한다.
여는 괄호: 스택에 추가
닫는 괄호: 스택 마지막 괄호와 짝 확인 후 제거문자열 끝까지 확인한 뒤 스택이 비어 있으면 올바른 괄호 문자열이다.
문자열 길이는 최대 1000이므로, 모든 회전 문자열을 만들고 각각 스택으로 검사하는 O(N^2) 풀이로 충분하다.
왼쪽 회전
왼쪽으로 x칸 회전한 문자열은 다음 두 부분을 이어 붙여 만들 수 있다.
rotated = s[x:] + s[:x]예를 들어 문자열이 다음과 같다고 하자.
s = "[]()"x가 1이면 다음과 같다.
s[1:] = "]()"
s[:1] = "["
회전 결과 = "]()["x는 0부터 문자열 길이 - 1까지 확인한다.
for x in range(len(s)):괄호 짝 정보
닫는 괄호를 키로, 짝이 되는 여는 괄호를 값으로 저장한다.
pairs = {
")": "(",
"]": "[",
"}": "{",
}닫는 괄호를 만났을 때 스택의 마지막 값과 pairs[character]를 비교하면 괄호 종류가 맞는지 확인할 수 있다.
stack[-1] == pairs[character]올바른 괄호 문자열 검사
여는 괄호
여는 괄호는 나중에 닫는 괄호와 짝을 맞춰야 하므로 스택에 넣는다.
if character in "([{":
stack.append(character)닫는 괄호인데 스택이 비어 있는 경우
닫는 괄호가 먼저 등장하면 짝을 맞출 여는 괄호가 없다.
if not stack:
return False예를 들어 다음 문자열은 첫 문자부터 올바르지 않다.
)(괄호 종류가 다른 경우
스택의 마지막 여는 괄호와 현재 닫는 괄호의 종류가 다르면 올바르지 않다.
if stack[-1] != pairs[character]:
return False예를 들어 다음 문자열은 괄호 순서는 맞는 것처럼 보이지만 종류가 다르다.
([)]짝이 맞는 경우
스택 마지막 괄호와 현재 닫는 괄호가 짝이면 스택에서 제거한다.
stack.pop()마지막 스택 확인
문자열을 모두 확인한 뒤 스택이 비어 있어야 모든 여는 괄호가 닫힌 상태다.
return not stack풀이 과정
- 문자열 길이가 홀수면 0을 반환한다.
- 0부터 문자열 길이 - 1까지 모든 회전 횟수를 확인한다.
- 슬라이싱으로 왼쪽 회전 문자열을 만든다.
- 스택으로 회전 문자열이 올바른지 검사한다.
- 올바른 문자열이면 정답을 1 증가시킨다.
Python 코드
def solution(s):
# 올바른 괄호 문자열은 길이가 항상 짝수다.
if len(s) % 2 == 1:
return 0
pairs = {
")": "(",
"]": "[",
"}": "{",
}
def is_correct(brackets):
stack = []
for character in brackets:
# 여는 괄호는 스택에 저장한다.
if character in "([{":
stack.append(character)
continue
# 닫는 괄호의 짝을 검사한다.
if not stack:
return False
if stack[-1] != pairs[character]:
return False
stack.pop()
return not stack
answer = 0
for shift in range(len(s)):
rotated = s[shift:] + s[:shift]
if is_correct(rotated):
answer += 1
return answer코드 설명
홀수 길이 예외 처리
if len(s) % 2 == 1:
return 0모든 올바른 괄호 문자열은 여는 괄호와 닫는 괄호가 같은 개수여야 한다.
따라서 문자열 길이가 홀수라면 어떤 회전을 해도 올바른 괄호 문자열이 될 수 없다.
pairs
pairs = {
")": "(",
"]": "[",
"}": "{",
}닫는 괄호가 나타났을 때 필요한 여는 괄호를 바로 찾기 위한 딕셔너리다.
스택의 마지막 값
stack[-1]가장 나중에 열린 괄호는 가장 먼저 닫혀야 한다.
따라서 괄호 짝 검사는 스택의 마지막 값만 확인하면 된다.
회전 문자열
rotated = s[shift:] + s[:shift]앞쪽 shift개의 문자를 문자열 뒤로 옮겨 왼쪽 회전을 구현한다.
shift가 0이면 원래 문자열을 그대로 검사한다.
예시
다음 문자열을 살펴보자.
s = "[](){}"왼쪽으로 회전한 결과 중 올바른 괄호 문자열인 경우는 다음과 같다.
0칸: [](){}
2칸: (){}[]
4칸: {}[]()다른 회전 결과는 닫는 괄호로 시작하거나, 괄호 짝이 맞지 않는다.
따라서 정답은 다음과 같다.
3시간 복잡도
문자열의 길이를 N이라고 하자.
모든 회전 횟수 N개를 확인하고, 각 회전 문자열을 검사하는 데 O(N)이 필요하다.
O(N^2)N은 최대 1000이므로 충분히 처리할 수 있다.
공간 복잡도
한 번의 괄호 검사에서 스택에 최대 N개의 괄호가 들어갈 수 있다.
O(N)회전 문자열을 만들기 위한 추가 문자열 공간도 O(N)이다.
정리
이 문제는 모든 회전 문자열을 만들고, 스택으로 올바른 괄호 문자열인지 검사하는 구현 문제다.
모든 왼쪽 회전 횟수 확인
여는 괄호는 스택에 추가
닫는 괄호는 스택 마지막 괄호와 종류 확인
문자열 끝에서 스택이 비어 있으면 올바른 문자열
올바른 회전 문자열의 개수 반환괄호의 개수만 비교하지 않고, 가장 나중에 열린 괄호가 먼저 닫혀야 한다는 스택의 특성을 이용하는 것이 핵심이다.
