👀 문제
https://leetcode.com/problems/longest-valid-parentheses/
👊 도전
1. 설계
- 이분탐색을 이용해 정렬된 구간이 어딘지 찾는다.
- 정렬된 구간에 target이 포함된다면 그곳으로, 아니라면 반대로 이동한다.
- mid로 target을 찾을 때 까지 반복한다.
2. 구현
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
/**
*
* @author HEESOO
*
*/
class Solution {
public int longestValidParentheses(String s) {
int left=0, right=0, answer=0;
for(int i=0;i<s.length();i++){ // -> 방향
char ch=s.charAt(i);
if(ch=='(') left++;
else right++;
if(left==right) answer=Math.max(answer, left*2);
else if(left<right) left=right=0;
}
left=0; right=0;
for(int i=s.length()-1;i>=0;i--){
char ch=s.charAt(i); // <- 방향
if(ch=='(') left++;
else right++;
if(left==right) answer=Math.max(answer, left*2);
else if(left>right) left=right=0;
}
return answer;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 왼쪽->오른쪽으로 순회한다
- 왼쪽->오른쪽으로 탐색하며 괄호의 개수를 센다.
- left(여는 괄호), right(닫는 괄호)가 같아지면 현재까지 카운트한 개수를 answer에 저장한다.
- 이때 answer에는 최댓값만을 넣기 위해 Math.max()를 이용한다.
- right 수가 더 많아지면 left, right를 초기화한다. ())와 같은 경우이기 때문에 뒤에 올바를 괄호 개수를 누적할 수 없다.
- 왼쪽<-오른쪽으로 순회한다
- 이번에는 거꾸로 순회하며 문자열을 체크한다.
- left, right 개수를 세고 같아지면 answer에 최댓값을 저장한다.
- left수가 많아지면 (()인 꼴이므로 left, right를 초기화한다.