https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/
stack
1. 문제 및 접근
921. Minimum Add to Make Parentheses Valid
가능한 괄호는 아예 비었거나 짝이 맞으면 됨
"())" 스택에 넣는데, 닫는 게 나오면 pop해주고, 남은 것들의 갯수를 세어주면 끝 ?
)로 시작할 수도 있다. (로만 시작한단 말이 없음
)면 지운다는 개념으로 다가가면 안될듯
그러면 각각 카운트 세주고 차이 만큼 반환? 안됨
"()))((" 면 값은 맞는데 여는 게 2개 닫는게 2개 필요하기 떄문에 안되네
Constraints:
- 1 <= s.length <= 1000
- s[i] is either '(' or ')'.
2. 틀린 풀이
처음에 문제가 바로 stack 문제라는 건 알았지만,
그냥 '(' 와 ')' 의 갯수를 구하고 그 차이의 절대 값만 반환해도 되지 않을까 생각했다.
바로 반례에 걸려서 그냥 stack으로 풀어야겠다..
"() )) ((" 갯수는 같으나 반대의 2개의 경우라 총 4개가 더 필요하다.
2개의 여는 기호, 2개의 닫는 기호 = 4번의 움직임
3. Stack 풀이
public int minAddToMakeValid(String s) {
Stack<Character> stack = new Stack<>();
int anyCount = 0;
for (int i = 0; i < s.length(); i++) {
char current = s.charAt(i);
if(current == '(') {
stack.push(current);
} else {
if (stack.size() != 00 && stack.peek() == '(') {
stack.pop();
} else
anyCount++;
}
}
return stack.size() + anyCount;
}
3-1. stack 및 count 변수
stack 선언,
그리고 만약에 ')'로 시작하거나, 또 짝이 다 맞는 상태에서 다시 ')'가 들어올 때 stack의 size에 더해 반환해줄 변수를 선언
count 변수의 용도는 밑에서 예를 들어 자세히 설명하겠다.
3-2. stack에 push or pop
들어온 s를 가지고 현재 char를 판별
현재 들어온 current 가 '(' 라면 ?
- stack에 push
현재 들어온 current 가 ')' 라면 ?
두가지 경우가 있다.
- stack이 비어 있지 않고, ')' 라면 짝이 있다는 뜻이다. stack에서 맞는 짝인 '('를 지워주기 위해 pop
- stack이 비어있다면 ? 현재 stack에는 쌓이지 않는 ')'가 들어왔다는 뜻이다 이럴 경우 stack으로 처리하지 않고, count를 세어주기
stack의 size와 아까 세어준 ')'의 갯수를 반환하면 끝
3-2. 예시
String s = "( ) ) ) ( ("
stack = [ ]
count = 0
1. i = 1, current = '('
- 현재 '('는 stack에 push
- stack = [ ( ]
- count = 0
2. i = 2, current = ')'
- 현재 ')' 는 stack에 비어있지 않아서, pop
- stack = [ ]
- count = 0
3. i = 3, current = ')'
- 현재 ')' 는 stack이 비어있으므로, count ++
- stack = [ ]
- count = 1
4. i = 4, current = ')'
- 현재 ')' 는 stack이 비어있으므로, count ++
- stack = [ ]
- count = 2
5. i = 5, current = '('
- 현재 '(' 는 stack에 push
- stack = [ ( ]
- count = 2
6. i = 6, current = '('
- 현재 '(' 는 stack에 push
- stack = [ ( , ( ]
- count = 2
stack의 size와 count를 세어서 반환하면 정답! = 4
4. 마무리
leetcode에서 설명 란에 예시를 들어 주는 게 추가의 예시였는데, 저게 정답인줄 알고 헷갈려서 열이 살짝 받을 뻔 했다~
보자마자 stack문제라는 걸 알 수 있어서 약간 우쭐했고, 문제가 미들러 수준은 아닌 것 같아서 여러 문제들을 더 풀어봐야겠네
둘다 O(N) 문제다.