[알고리즘] Brackets 문제에서 "균형카운트" 기법보다 더 나은 기법 -> "Stack"
우연히 Brackets 라는 알고리즘 문제를 접했습니다.
살짝 놀랐습니다. 제가 일할 때 구현해야 했던 절차적 문자열 조합 문제 상황과 유사했거든요. 저는 배치에 대한 표현식 규칙을 만들고 조합하는 과정에서 문자열 규칙 검증이 필요했어서 구현했었습니다. 제 경우는 추가적인 문제를 해결하고자, 절차적으로 해야 했기 때문에 재귀함수를 썼었는데요,
이 Brackets 문제도 그와 비슷해보여서 재귀함수 방식으로 해결해보려고 했습니다. 그런데 역시나 만만치 않게 복잡하더군요. 심지어 문제를 틀리기까지..
아래는 제 풀이입니다. 좀 복잡하고 틀렸어요 ㅎㅎ Easy문제인데!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 괄호가 잘 닫혀있는지 판단하는 문제
# 잘 닫혔으면 1, 닫히지 않았으면 0
# ([)()] 일 경우에는 짝이 맞아도 잘 닫히지 않은 것.
# (([)()]) 여도 닫히지 않은 것.
# 맨 앞, 맨 뒤를 꺼내서 각각 여는 괄호인지, 닫는 괄호인지, 짝이 맞는지 판단하고
# 바깥부터 소거하는 재귀함수.
def isOpen(C)-> bool:
return C in ['(', '[', '{']
def isClose(C)-> bool:
return C in [')', ']', '}']
def matchStr(C)-> str:
if C=='(': return ')'
if C=='[': return ']'
if C=='{': return '}'
else: return ""
# S != "" 이다.
# S를 받아서 길이가 2개 이상이고, 맨 앞이 여는 괄호라면,
# 그 뒤의 괄호들을 짝이 잘 맞을때까지 세다가
# 맨 처음으로 닫는 짝괄호가 나오면
# 그 맨앞 맨뒤를 unwrap하고 안의 si, so에 대해서 unwrap을 재귀적으로 해서 성공여부를 모두 판단해 success:bool을 내보낸다.
# So가 없으면 ""이다.
# unwrap이 실패하면 false를 내보낸다.
# unwrap을 하고 나온 결과가 success라면 계속해서 Si와 So에 대해서도 unwrap을 진행한다.
# 실패(false)가 나오면 최종 리턴은 0이다. 성공이면 1이다.
def unwrap(S)-> bool:
if len(S) < 2:
return False
else:
co = S[0]
rest = S[1:]
if not isOpen(co):
return False
else:
# 열려있으니까 계속
# 맨 처음으로 짝 괄호가 나오기까지 찾아서 si, so, success를 정한다.
cc = matchStr(co)
for i in range(len(rest)):
if rest[i] == cc:
si = rest[:i]
if i+1 != len(rest):
so = rest[i+1:]
else:
so = ""
success = True
if si != "":
res:bool = unwrap(si)
if not res: return False
if so != "":
res:bool = unwrap(so)
if not res: return False
return True
def solution(S):
# print(isClose(S[0]))
# print(matchStr('['))
if unwrap(S):
return 1
else:
return 0
그래서 gpt에게 물어보니, 스택(Stack)으로 풀어야 한다고 합니다. 스택으로 풀면 시간복잡도가 O(N), 재귀적으로 풀면 시간복잡도가 O(N^2)이고 코드도 간단.
제가 위에서 풀었던 알고리즘은 “균형카운트” 방식이라고 합니다. gpt의 설명을 덧붙이겠습니다.
굳이굳이 균형카운트로 풀기
인덱스 기반(슬라이싱 없이) 구현 예시 (맞는 풀이)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def match_of(c):
return { '(':')', '[':']', '{':'}' }.get(c, '')
def is_open(c):
return c in '([{'
def check(S, l, r):
# S[l:r] 구간 검사 (r은 배타)
if l == r: # 빈 문자열은 올바름
return True
if not is_open(S[l]): # 맨 앞이 여는 괄호가 아니면 실패
return False
open_c = S[l]
close_c = match_of(open_c)
cnt = 1
i = l + 1
# open_c와 close_c에 대해서만 균형 카운트로 짝 위치 찾기
while i < r:
if S[i] == open_c:
cnt += 1
elif S[i] == close_c:
cnt -= 1
if cnt == 0:
# 경계: (U) | W
return check(S, l + 1, i) and check(S, i + 1, r)
i += 1
# 끝까지 가도 짝을 못 찾음
return False
def solution_balance_split(S):
return 1 if check(S, 0, len(S)) else 0
이제 정석인 스택으로 풀기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# {[()()]} 는 성공. 열고 닫는 짝이 맞음.
# ([)()] 는 실패. 열고 닫는 짝이 안맞음.
# 하나씩 보면서, 가장 최근에 열은 짝 닫힘이 가장 처음 나오는지 검사해야 함.
# 열기 -> 짝 찾음 -> 닫기
# open2close:dict[str:str]
# 구현법: 순서대로 보면서 열림짝이면 스택에 넣어서 스택이 비어있지 않으면 마지막 넣은 top의 닫힘짝과 비교하려는 닫힘짝이 같은지 봐야함.
# 같으면 스택 pop해서 top을 꺼내고, 계속 진행. 스택이 빌 때까지 전부 진행하면 1 반환.
# 다르면 틀리므로 0 반환
def solution(S):
open2close:dict[str:str] = {'(':')', '{':'}','[':']'}
opens = set(open2close.keys())
stack:list[str] = []
# 순서대로 보면서
for char in S:
# 열림짝이면 스택에 넣자.
if char in opens:
stack.append(char)
# 닫힘짝인데
# 근데 스택이 비어있으면? 잘못된것이므로 0 반환
if not stack:
return 0
# 스택의 마지막의 짝과 같은지 비교한다. 같으면 스택 pop해서 top을 꺼내고 계속 진행.
if open2close[stack[-1]] == char:
stack.pop()
# 다 마치고 스택이 전부 비었으면 성공.
if not stack:
return 1
else:
return 0
이걸 이제 알다니 ㅎㅎ 이제라도 알게되서 럭키..
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.