문제 설명
다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
(), [], {} 는 모두 올바른 괄호 문자열입니다.
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
s의 길이는 1 이상 1,000 이하입니다.
입출력 예
s result
"[](){}" 3
"}]()[{" 2
"[)(]" 0
"}}}" 0
입출력 예 설명
입출력 예 #1
다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.
x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?
0 "[](){}" O
1 "](){}[" X
2 "(){}[]" O
3 "){}[](" X
4 "{}[]()" O
5 "}[](){" X
올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.
입출력 예 #2
다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.
x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?
0 "}]()[{" X
1 "]()[{}" X
2 "()[{}]" O
3 ")[{}](" X
4 "[{}]()" O
5 "{}]()[" X
올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.
입출력 예 #3
s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.
입출력 예 #4
s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.
풀이
파이썬에서 깊은 복사 얕은 복사 개념을 까먹어서 애를 먹었다. 깊은 복사는 A를 복사한 B가 있으면 B를 수정하면 A도 같이 수정되는 개념이다. 해당 문제에서는 얕은 복사를 통해 A,B를 각각 관리해야한다.
먼저 해당 문제를 풀기위해서는 스택과 큐의 개념을 알아야한다. 스택은 FILO으로 선입후출 개념이다.
또 큐는 FIFO으로 선입선출 구조이다. 해당 개념을 이해하면 문제는 쉽게 풀 수 있다.
어떻게?
append()와 pop()을 통해!
스택 리스트는 짝이 맞는 지 검사하기 위한 리스트이다.
우선 짝을 검사하기 위해 문자를 저장할 slist에서 문자 한개씩 꺼낸다. (pop(0))
*pop(0)은 맨 앞에 있는 문자를 꺼내준다.
이후 "[", "{", "(" 와 같이 열리는 문자를 만났을 때 스택 리스트에 추가한다(append)
또는 "]", "}", ")" 와 같이 닫히는 문자를 만났을 때는 저장된 스택 리스트에서 문자를 하나씩 꺼내
* (pop()) *pop()은 맨 뒤 문자를 꺼내준다.
"[]", "()", "{}" 와 맞는 지 비교를 한다. 맞지 않으면 False를 리턴한다. 또 생각할 것은 스택 리스트가 비어있는 상태에서 닫힌 문자를 만나면 이것 또한 짝이 맞지 않으므로 False를 리턴한다. 마지막으로 "{"와 같이 열린 문자만 들어왔을 경우 어느 조건문에 걸리지 않으므로 함수 마지막에 스택 리스트와 slist가 비어있는 지 확인해줘야 한다. 모두 비어있으면 True !
def check(slist):
stack=[]
s=slist.copy() # 얕은 복사
for i in range(len(s)):
c1=s.pop(0) # 맨 앞 문자를 꺼냄
if(c1=="{" or c1=="(" or c1=="["): # 열린 문자일 경우
stack.append(c1) # 스택 리스트에 저장
elif(c1): # 닫힌 문자일 경우
if(len(stack)>0):
c2=stack.pop() # 맨 뒤 문자를 꺼냄
else: # 스택 리스트가 비어있는 경우
return False
if not (c2+c1=="[]" or c2+c1=="{}" or c2+c1=="()"):
return False
if(len(stack)==0 and len(s)==0): # 리스트가 모두 비었는 지 체크
return True
else:
return False
def solution(s):
answer = 0
slist=list(s)
for i in range(len(slist)):
# 괄호 회전
c=slist.pop(0)
slist.append(c)
if(check(slist)):
answer+=1
return answer
좋은 코드
스택, 큐 구조를 사용하지 않고 단순 replace만으로 문제를 푸는 방법도 있었다!
while 문으로 문자열에 "()", "[]", "{}"이 있으면 계속해서 지우는 형식이다. 괄호 회전 또한 인덱싱을 통해 쉽게 접근하는 방법도 정말 좋은 접근 방법인 것 같다!
thanks for stone1098
def check(s):
while True:
if '()' not in s and '[]' not in s and '{}' not in s:
break
s = s.replace('()', '')
s = s.replace('[]', '')
s = s.replace('{}', '')
return 1 if len(s) == 0 else 0
def solution(s):
answer = 0
for i in range(len(s)):
answer += check(s)
s = s[1:] + s[0]
return answer
'Python > 백준 알고리즘 (파이썬)' 카테고리의 다른 글
[11660] 구간 합 구하기 5 (2) | 2023.10.18 |
---|---|
[프로그래머스] 크레인 인형뽑기 게임 (0) | 2023.07.25 |
[프로그래머스] 공원 산책 (0) | 2023.07.13 |
[프로그래머스] 신고 결과 받기 (2) | 2023.07.12 |
[프로그래머스] 달리기 경주 (0) | 2023.07.12 |