이전에 괄호변환과 너무 비슷한 유형이었다. 그래서 그때 사용했던 풀이법을 그대로 사용했는데, 테스트 케이스에서 틀려버렸다.
이전에 괄호 변환시 사용했던 풀이법이 정석은 아니었다. 스택을 사용하는게 정석이었다. 스택을 사용한 풀이법이 약한 경우가 있어서, 스택을 활용한 문제를 다시 풀어봐야할 필요성을 느꼈다.
그리고, 항상 느끼지만 대부분의 문제가 카카오 문제를 활용한 것이 매우 느껴진다. 카카오 문제를 공들여서 풀어놔야겠다.
복습해야 할 유형과 문제들을 정리해놔야지 ...
1. 문제 설명
[](){} 이러한 형태의 문자열이 주어진다. 그리고 문자열을 왼쪽으로 x만큼 회전시킨다.
0번만큼 회전시키면 그대로, 1번만큼 회전시키면 ](){}[ 이 된다.
이런식으로 문자열의 길이-1 까지 계속 회전시킨다.
각각 회전시킨 문자열에 대해 올바른 문자열인지 확인한다.
올바른 문자열의 조건은 문제에서 다음과 같다.
- (), [], {} 는 모두 올바른 괄호 문자열입니다.
- 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
- 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
즉, 간단히 말해서 짝이 맞아야 한다.
2. 어려웠던 점
1) 괄호 변환 문제
괄호 변환 문제에서도 동일하게 올바른 괄호 문자열인지 확인했었기 때문에, 그대로 해당 코드를 사용해서 풀이했다.
하지만 이렇게 하면, 문제가 발생했다. 이전 문제에서는 괄호가 ()인 경우만 있었지만 이 문제에서는 {[(의 여러가지 경우가 있었다. 그래서 단순히 카운팅하는 로직만 사용하면 {] 의 경우에도 문제가 없어졌다.
그래서, {},[], () 경우를 모두 따로 추출해서 카운팅했다.
그랬더니 ([{)}] 이런경우가 있더라. (테스트 케이스 14번이 통과가 안됐음 ;;)
질문게시판을 찾아보니 스택으로 푸는것이 정석이라고 했다.
그래서 풀이방식을 확인했다.
스택을 사용하는 문제는 대부분 마지막 원소와 비교하는 로직이다.
내가 스택을 활용하는 문제에 약하다는 것이 느껴짐.. 아무튼
3. 풀이법
1) 1차 풀이
import re
def confirm_alright(s_list):
cnt = 0
for i in s_list:
if cnt < 0:
return False
if i == "(" or i == "{" or i == "[":
cnt += 1
else:
cnt -= 1
if cnt == 0:
return True
return False
def solution(s):
cnt = 0
for i in range(len(s)):
u = s[:i]
v = s[i:]
first_result = confirm_alright(re.findall("{|}", v + u))
second_result = confirm_alright(re.findall("\[|\]", v + u))
third_result = confirm_alright(re.findall("\(|\)", v + u))
if first_result and second_result and third_result:
cnt += 1
return cnt이게 ([{)}] 이런경우를 고려하지 못했던 점이었다.
2) 2차 풀이
def check(str_list):
stack = []
for _str in str_list:
if _str in ('[', '(', '{'):
stack.append(_str)
else:
if not stack: return False
x = stack.pop()
if _str == ']' and x != '[':
return False
elif _str == ')' and x != '(':
return False
elif _str == '}' and x != '{':
return False
if stack: return False
return True
def solution(s):
cnt = 0
for i in range(len(s)):
u = s[:i]
v = s[i:]
if check(v+u):
cnt +=1
return cnt
스택을 활용한 풀이이다. [{( 가 있으면 모두 스택에 넣고 그 반대방향이 나온 순간 짝인지를 확인하는 것이다.
(을 마지막으로 넣었고, 그 다음에 반대 방향이 나온다면 그것은 반드시 ) 여야 한다.
그리고 )를 스택에 넣지 않고, 앞의 (를 pop하면 된다.
