Longest Valid Parentheses
(와 ) 문자만으로 이루어진 문자열 s가 주어집니다. 올바르게 구성된 가장 긴 부분 문자열(연속된 문자들의 구간)을 찾으세요. 부분 문자열 안의 모든 (는 그 뒤에 나오는 )로 닫혀야 하며, (()())처럼 괄호 쌍이 올바르게 중첩되어야 합니다. 해당 부분 문자열의 길이를 반환하고, ()조차 나타나지 않으면 0을 반환하세요.
함수
- sstring
- ( 및 ) 문자로 이루어진 문자열
- 반환값integer
- 가장 긴 올바른 형식의 부분 문자열의 길이 또는 그러한 부분 문자열이 없으면 0
제약 조건
1 ≤ s.length ≤ 6 × 104- s의 모든 문자는
(또는)입니다.
예제
- 입력
- s = "()(())"
- 출력
- 6
- 설명
- 문자열 전체가 올바른 형식입니다.
()뒤에(())가 옵니다. 올바른 형식의 두 조각을 나란히 놓으면 하나의 올바른 형식의 조각이 되므로, 답은 6개 문자 모두입니다.
- 입력
- s = "())((())"
- 출력
- 4
- 설명
- 인덱스 2의
)에는 짝이 없으므로 어떤 답도 이를 넘어갈 수 없고, 인덱스 3의(는 닫히지 않습니다. 가장 긴 부분 문자열은 인덱스 4부터 7까지의(())이며, 길이는 4로 시작 부분의()보다 깁니다.
- 입력
- s = "))(("
- 출력
- 0
- 설명
)두 개 모두(두 개보다 먼저 나오므로, 어떤(도 닫히지 않습니다. 올바른 형식의 부분 문자열은 없으며 답은 0입니다.
제출 시 숨은 테스트 +21개
후속 질문
가장 긴 올바른 형식의 부분 문자열이 시작하는 위치도 알려줄 수 있나요? 길이가 같은 부분 문자열이 여러 개라면 가장 왼쪽에 있는 것을 선택하세요.
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
부분 문자열을 왼쪽에서 오른쪽으로 읽으며 균형값을 유지합니다.
(에는 +1,)에는 -1을 더합니다. 올바른 형식의 부분 문자열에서는 균형값이 어떻게 되며, 균형값을 0 미만으로 떨어뜨리는)는 이 문자를 가로지르는 모든 부분 문자열에 대해 무엇을 알려 주나요?아직 닫히지 않은
(문자의 인덱스를 스택에 저장하세요.)가 맨 위의 문자를 닫으면, 여기서 끝나는 올바른 형식의 연속 구간은 이제 맨 위에 남은 인덱스 바로 다음에서 시작합니다. 열린 문자가 없을 때는 스택에 무엇을 넣어야 할까요?문자열 바로 앞의 인덱스인 -1로 스택을 시작합니다. 모든
(의 인덱스를 푸시합니다.)를 만나면 팝합니다. 스택이 비어 있으면 이)는 절대 짝을 찾을 수 없으므로, 해당 인덱스를 새로운 기준으로 푸시합니다. 그렇지 않으면 현재 유효한 구간의 길이는i에서 스택 맨 위의 인덱스를 뺀 값입니다. 측정한 구간 중 가장 긴 것을 유지합니다.
풀이
문자열 하나만 확인할 때보다 더 어려워지는 이유는 두 가지입니다. 올바른 괄호 조각은 서로 맞닿아 있으면 이어지므로, ()와 (())가 나란히 있으면 길이가 6인 하나의 연속 구간으로 계산됩니다. 그리고 ())(())의 )처럼 불필요한 문자가 하나 있으면 문자열이 끊기므로, 그 문자를 가로지르는 답은 없습니다. 시작 위치를 모두 테스트하면 O(n²)의 비용이 듭니다. 해결 방법은 현재 연속 구간이 어디서 시작했는지 기억하는 것입니다. 맨 아래에 기준 표시가 있는 인덱스 스택을 사용하면 한 번의 순회로 처리할 수 있고, 단순한 카운터로 두 번 순회하면 스택을 전혀 쓰지 않고 처리할 수 있습니다.
각 시작 위치에서 부분 문자열을 확장하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
부분 문자열을 왼쪽에서 오른쪽으로 읽으며, (에 1을 더하고 )에 1을 빼는 균형값을 유지합니다. 균형값이 한 번도 0 아래로 내려가지 않고 0으로 끝날 때에만 부분 문자열이 올바른 괄호열입니다. 0 아래로 내려간다는 것은 닫을 열린 괄호가 없는 상태에서 )가 나왔다는 뜻입니다.
그러니 시작 위치를 고정하고 오른쪽으로 이동하면서 한 번에 문자 하나씩 균형값을 갱신합니다. 균형값이 0으로 돌아올 때마다 시작 위치부터 현재 위치까지의 구간은 올바른 괄호열이므로 길이를 기록합니다. 균형값이 0 아래로 내려가는 순간 멈춥니다. 해당 )는 이 시작 위치에서 더 긴 어떤 구간을 보더라도 짝을 찾지 못하기 때문입니다. 모든 올바른 부분 문자열에는 시작 위치가 있고, 그 부분 문자열의 모든 끝 위치를 확인하므로 놓치는 것이 없습니다.
문제는 비용입니다. ( 59998개 뒤에 ()가 오는 문자열에서는 균형값이 0 아래로 내려가지 않으므로 모든 시작 위치에서 끝까지 이동합니다. n = 6 × 10^4일 때 약 n²/2 = 1.8 × 10^9번의 연산이 필요합니다. 큰 테스트는 이런 식으로 만들어져 있습니다. (각 부분 문자열을 늘려 가는 대신 처음부터 확인하면 더 나쁩니다. O(n³)입니다.)
알고리즘
best를 0으로 설정합니다.- 각 시작 위치에 대해
balance를 0으로 설정하고, 시작 위치부터 마지막 문자까지 끝 위치를 이동합니다. (이면 1을 더하고)이면 1을 뺍니다.balance가 0보다 작으면 이 시작 위치의 탐색을 중단합니다. 0이면 구간 길이end - start + 1로best를 갱신합니다.best를 반환합니다.
def longestValidParentheses(s):
best = 0
for start in range(len(s)):
balance = 0
for end in range(start, len(s)):
balance += 1 if s[end] == "(" else -1
if balance < 0:
# A ')' without a partner: no longer run starts here
break
if balance == 0:
best = max(best, end - start + 1)
return best기준 표시자가 있는 인덱스 스택
핵심 아이디어
스택을 사용해 괄호를 짝짓는 방법은 익숙합니다. 각 (를 푸시하고, )마다 하나를 팝합니다. 여기서는 길이도 필요하므로 인덱스를 푸시하고, 스택 맨 아래에 인덱스를 하나 더 둡니다. 이것은 현재 구간 바로 앞의 위치인 기준점입니다. 시작할 때는 아무것도 읽지 않았으므로 기준점은 -1입니다.
(를 만나면 해당 인덱스를 푸시합니다. )를 만나면 팝합니다. 두 가지 경우가 생길 수 있습니다. 스택이 이제 비어 있다면 기준점을 팝한 것이므로, 이 )를 닫을 괄호가 없었던 것입니다. 올바른 부분 문자열에는 이것이 포함될 수 없으므로 이 인덱스가 새 기준점이 됩니다. 해당 인덱스를 푸시하세요. 그렇지 않으면 맨 위에 남은 인덱스는 i에서 끝나는 구간 바로 앞의 마지막 문자입니다. 아직 닫히지 않은 (이거나 기준점입니다. 그 뒤부터 i까지는 모두 짝이 맞으며, 이 구간은 더 왼쪽으로 이어질 수 없으므로 길이는 i - top입니다.
다음은 ())((())의 예입니다.
i = 0,(: 0을 푸시합니다. 스택은[-1, 0]입니다.i = 1,): 0을 팝합니다. 맨 위는 -1이므로 구간 길이는1 - (-1) = 2입니다.i = 2,): -1을 팝하면 스택이 비게 됩니다. 이)에는 짝이 없으므로 새 기준점으로 2를 푸시합니다. 스택은[2]입니다.i = 3, 4, 5,(세 개: 이들을 푸시합니다. 스택은[2, 3, 4, 5]입니다.i = 6,): 5를 팝합니다. 맨 위는 4이므로 구간 길이는6 - 4 = 2입니다.i = 7,): 4를 팝합니다. 맨 위는 3이므로 구간 길이는7 - 3 = 4이며, 이것이 답입니다.
기준점 덕분에 맞닿아 있는 구간을 하나로 합칠 수 있습니다. ()(())에서는 첫 번째 쌍의 길이가 1 - (-1) = 2이고, 마지막 )는 인덱스 2를 팝한 뒤 맨 위에서 다시 -1을 찾으므로 길이를 5 - (-1) = 6으로 계산합니다. 짝이 맞는 (부터 측정하면 4가 되어 앞에 있는 ()를 놓치게 됩니다. 각 인덱스는 최대 한 번씩 푸시되고 팝되므로 한 번의 순회에 O(n)이 걸리며, 스택에는 최대 n+1개의 인덱스가 들어갈 수 있습니다.
알고리즘
- -1을 담은 스택으로 시작하고
best를 0으로 설정합니다. - 각 인덱스
i에 대해s[i]가(이면i를 푸시합니다. )이면 한 번 팝합니다.- 스택이 이제 비어 있으면 새로운 기준점으로
i를 푸시합니다. 그렇지 않으면i - top으로best를 갱신합니다. best를 반환합니다.
def longestValidParentheses(s):
# The bottom of the stack is the index just before the current run
stack = [-1]
best = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack:
# This ')' has no partner: it becomes the new base
stack.append(i)
else:
best = max(best, i - stack[-1])
return best두 번의 패스로 열기와 닫기 개수를 세세요
핵심 아이디어
스택은 현재 구간이 어디서 시작되었는지만 알려 줍니다. 카운터 두 개로도 알 수 있습니다. 왼쪽에서 오른쪽으로 이동하면서 마지막 초기화 이후의 opens와 closes를 셉니다. 두 값이 같으면 초기화 이후의 모든 문자가 올바른 괄호열이며, 길이는 2 × closes입니다. closes가 앞서면 )에 짝이 없는 것이고, 이는 스택에서 기준점이 사라진 순간과 같으므로 두 카운터를 모두 0으로 초기화합니다.
한 번의 순회로는 충분하지 않습니다. 닫히지 않는 (가 있으면 opens가 계속 앞서고, 카운트가 다시 같아지지 않습니다. (()에서는 왼쪽 순회가 열린 괄호 2개와 닫힌 괄호 1개로 끝나 아무것도 찾지 못하지만, 바로 그 안에 ()가 있습니다. 따라서 역할을 바꿔 오른쪽에서 왼쪽으로 두 번째 순회를 합니다. 이번에는 opens가 앞서면 초기화합니다. 거꾸로 읽으면 (()는 닫힌 괄호, 열린 괄호(같아짐: 길이 2), 그리고 초기화를 일으키는 열린 괄호 순서입니다. 정답은 두 순회에서 얻은 값 중 더 큰 값입니다.
두 번의 순회로 모든 구간을 찾을 수 있는 이유는 가장 긴 구간의 양쪽 경계가 짝을 이룰 수 없는 문자이거나 문자열의 끝이기 때문입니다. 왼쪽 경계가 짝이 없는 )이거나 문자열의 시작이라면, 왼쪽 순회는 구간이 시작되는 지점에서 초기화되고 끝나는 지점에서 카운트가 같아지는 것을 확인합니다. 왼쪽 경계가 짝이 없는 (라면, 오른쪽 경계는 )일 수 없습니다. 그 )가 짝이 없는 (를 닫아 구간이 더 길어지기 때문입니다. 따라서 오른쪽 경계는 짝이 없는 (이거나 문자열의 끝이며, 오른쪽 순회가 같은 방식으로 해당 구간을 찾습니다. 각 순회는 정수 두 개를 사용해 문자열을 한 번 읽으므로 시간 복잡도는 O(n)이고 추가 메모리 사용량은 O(1)입니다.
알고리즘
best를 0으로 설정하고,opens와closes도 0으로 설정합니다.- 왼쪽에서 오른쪽으로 이동하면서 각 문자를 셉니다. 개수가 같으면
2 × closes로best를 업데이트합니다.closes가 더 크면 둘 다 0으로 재설정합니다. - 두 카운터를 재설정한 다음, 이번에는
opens가 더 클 때 재설정하는 점만 제외하고 같은 방식으로 오른쪽에서 왼쪽으로 이동합니다. best를 반환합니다.
def longestValidParentheses(s):
best = 0
# Left to right: more ')' than '(' ends every run that started earlier
opens = closes = 0
for ch in s:
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * closes)
elif closes > opens:
opens = closes = 0
# Right to left: catches the runs that an unmatched '(' hid from the first pass
opens = closes = 0
for ch in reversed(s):
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * opens)
elif opens > closes:
opens = closes = 0
return best
함정과 경계 사례
대부분의 오답은 올바른 쌍을 잘못된 위치에서 세거나, 연속 구간의 시작점을 놓칩니다.
- 문자열 전체에서 짝이 맞는 쌍을 세는 경우.
())((())에는 쌍이 3개 있지만, 모두 서로 붙어 있지는 않으므로 답은 6이 아니라 4입니다. - 짝이 맞는
(부터 연속 구간의 길이를 재는 경우.()(())에서 마지막)는 인덱스 2와 짝이 맞으므로 길이가 4가 되고, 앞에 있는()를 놓칩니다. pop 이후 스택에 남은 인덱스부터 길이를 재세요. - 스택을 비운 상태에서 시작하는 경우. 그러면
())의 첫 번째)는 길이를 잴 기준이 없고, 짝이 맞지 않는)는 빈 스택에서 pop을 시도합니다. -1을 기준값으로 두면 두 문제가 모두 해결됩니다. - 카운터를 한 방향으로만 실행하는 경우.
(()는 왼쪽에서 오른쪽으로 탐색하면 0을 반환하고,())는 오른쪽에서 왼쪽으로 탐색하면 0을 반환합니다. 둘 다 답은 2입니다. - 카운터가 같아졌을 때 초기화하는 경우.
()()처럼 개수가 같아도 연속 구간은 계속 늘어날 수 있습니다. 한쪽 개수가 다른 쪽보다 많아질 때만 초기화하세요. - Lua와 R에서는 인덱스가 1부터 시작하므로, 첫 번째 기준값은 -1이 아니라 0입니다.
자주 묻는 질문4
Longest Valid Parentheses의 시간 복잡도는 얼마인가요?
스택 풀이와 두 번 순회하는 카운터 풀이 모두 각 문자를 일정한 횟수만큼 읽으므로 O(n) 시간에 실행됩니다. 스택은 최악의 경우, 예를 들어 (만으로 이루어진 문자열에서 O(n)의 메모리가 필요하지만, 카운터는 O(1)이 필요합니다. 모든 시작 위치를 시도하면 O(n²)입니다.
스택은 왜 -1에서 시작하나요?
연속 구간의 길이는 현재 인덱스에서 연속 구간 바로 앞 인덱스를 뺀 값입니다. 인덱스 0에서 시작하는 연속 구간의 경우, 그 이전 인덱스는 문자열에서 한 칸 앞인 -1입니다. 먼저 -1을 푸시하면 짝이 맞는 )가 길이를 측정할 때 스택이 비어 있지 않고, 짝이 맞지 않는 )가 이를 팝하면 해당 )가 새로운 기준이 됩니다.
Longest Valid Parentheses를 위한 동적 프로그래밍 해법이 있나요?
네. end[i]를 인덱스 i에서 끝나는 가장 긴 올바른 형식의 부분 문자열의 길이라고 하자. s[i]가 (이면 값은 0이다. s[i-1]이 (이면 end[i] = end[i-2] + 2이다. )라면 i-1에서 끝나는 연속 구간 바로 앞의 문자 j = i - end[i-1] - 1을 살펴본다. s[j]가 (이면 그 문자가 해당 구간을 감싸며, end[i] = end[i-1] + 2 + end[j-1]이다. 여기서 마지막 항은 왼쪽에서 맞닿아 있는 구간을 이어 붙인다. 답은 가장 큰 end[i]이며, 시간과 메모리 복잡도는 O(n)이다.
카운터를 사용해 한 번만 순회하는 것으로는 왜 충분하지 않을까요?
왼쪽에서 오른쪽으로 진행하는 순회는 )의 개수가 (보다 많아질 때만 초기화됩니다. 닫히지 않는 여분의 (가 하나 있으면 문자열의 나머지 부분에서 개수가 계속 어긋나므로, 순회 중 두 개수가 같아지는 경우가 없습니다. (()에서는 여는 괄호 2개와 닫는 괄호 1개로 끝나며 아무것도 찾지 못합니다. 오른쪽에서 왼쪽으로 읽으면 첫 번째 순회에서 여분의 )를 처리하는 것과 같은 방식으로 여분의 (를 처리하므로, 두 순회를 함께 수행하면 모든 연속 구간을 확인할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def longestValidParentheses(s):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
s = "()(())"
기대값
6