반응형
소괄호만 사용되었다는 가정하에 가장 긴 완성된 괄호를 세는 문제 입니다.
먼저 스택을 사용하는 방법입니다.
스택에는 지금까지 읽은 열린 괄호의 위치를 저장하며, 추가로 이전까지 완성된 소괄호 정보도 필요합니다.
def longestValidParentheses(s):
strLen = len(s)
dp = [0] * (strLen + 1)
stack = []
ans = 0
for i in range(strLen):
c = s[i]
if (c == '('):
stack.append(i)
else:
if len(stack) > 0:
pos = stack.pop()
cnt = i - pos + 1
if pos > 0:
cnt += dp[pos - 1]
if (cnt > ans):
ans = cnt
dp[i] = cnt
return ans이 방법은 루프를 한번 돌면서 처리가 된다는 장점이 있지만, 이전 값을 저장하는 dp와 괄호의 시작을 stack에 담아두어야 하기 때문에 메모리 공간을 많이 차지합니다.
이를 개선한 방법은 다음과 같습니다.
루프를 돌며, 열린 괄호와 닫힌 괄호의 수를 카운트 합니다.
왼쪽에서 오른쪽으로 진행할 때는 닫힌 괄호의 수가 더 많으면 모든 괄호의 카운트를 0으로 두고 새로 카운트 합니다.
열린 괄호와 닫힌 괄호의 수가 같으면 완성된 괄호의 숫자가 나옵니다.
여기서 문제는 처음에 열린 괄호가 더 많이 나와서 닫힌 괄호 수와 일치 하지 않고 끝나면 완성된 괄호의 수가 0으로 됩니다.
따라서 문제를 해결하기 위해서 반대방향으로 한번 더 진행합니다.
이번에는 열린 괄호가 더 많으면 모든 괄호의 카운트를 0으로 두고 새로 카운트 합니다.
두 번째 루프에서는 처음에 닫힌 괄호가 더 많이 나오는 경우 카운트가 되지 않지만, 첫 번째 루프에서 이미 카운트가 되었기 때문에 두 번의 결과의 최대값을 선택하면 됩니다.
def longestValidParentheses(s):
max = 0
l, r = 0, 0
for c in s:
if c == '(':
l += 1
else:
r += 1
if (r > l):
l, r = 0, 0
elif (r == l and r > max):
max = r
for c in s[::-1]:
if c == '(':
l += 1
else:
r += 1
if (r < l):
l, r = 0, 0
elif (r == l and l > max):
max = l
return max * 2
변수를 추가하면 루프 한번으로 처리도 가능합니다.
def longestValidParentheses(s):
max = 0
l1, r1, l2, r2 = 0, 0, 0, 0
strLen = len(s)
for i in range(strLen):
if s[i] == '(':
l1 += 1
else:
r1 += 1
if (r1 > l1):
l1, r1 = 0, 0
elif (r1 == l1 and l1 > max):
max = r1
if s[strLen - 1 - i] == '(':
l2 += 1
else:
r2 += 1
if (r2 < l2):
l2, r2 = 0, 0
elif (r2 == l2 and l2 > max):
max = l2
return max * 2
반응형
'알고리즘 (기초 강좌)' 카테고리의 다른 글
| 가장 긴 증가 순서 (longest increasing subsequence) (0) | 2021.11.16 |
|---|---|
| Boyer-Moore 과반수 투표 알고리즘 (0) | 2021.11.11 |
