LeetCode 문제 중 난이도 Medium인 Minimum Add to Make Parentheses Valid이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.
문제해석
'('와 ')'로 이루어진 문자열 S에 최소로 괄호기호를 더해서 결과값이 유효하게 만든다.
유효한 괄호 문자열이란
- 빈 문자열 이거나,
- A와 B가 각각 유효한 괄호 문자열일때 AB를 연결한 형태이거나,
- A가 유효한 문자열일때 (A)의 형태인것
유효한 괄호문자열로 만들기 위해서 추가해주어야 할 최소한의 괄호기호의 개수를 구하여라.
스택(Stack) 자료구조를 이용해서 문제를 해결해보자. 스택은 FILO(First In Last Out)의 특징을 가진 자료구조이다. 책을 겹겹이 쌓는것을 상상해보자. 맨 위에 책을 올려놓거나 맨 위에 있는 책을 치울 수 있다. 아래에 있는 책을 꺼내려면 먼저 그 위의 책들을 전부 치워야 한다.
push(value) : value를 스택의 마지막 데이터 위치에 삽입
pop() : 스택 마지막 삽입된 데이터 제거
peek() : 스택 마지막 삽입된 데이터 값 확인
문제에서 괄호가 제대로 열리고 닫히려면
1 괄호를 연만큼 닫아주어야 한다. → '('와 ')'의 갯수가 같아야 함
2 먼저 열어준 뒤에 닫아주어야 한다. → '))(('은 유효한 괄호문자열이 아님
문자열 S를 탐색하면서 i번째 문자가 '('이면 스택에 넣어주자. i번째 문자가 ')'인 경우 스택에 들어있는 '('문자를 제거해준다. 스택이 비어있어서 제거할 '('가 없다면 answer+1을 해주자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public int minAddToMakeValid(String S) { Stack<Character> stack = new Stack<>(); int answer=0; for(int i=0 ; i<S.length() ; i++){ if(S.charAt(i)=='('){ stack.push(S.charAt(i)); }else if(stack.empty()){ result++; }else{ stack.pop(); } } return answer + stack.size(); } } | cs |
answer는 필요한 '('의 개수이고 stack에 들어있는 '('만큼 ')'도 필요하다. 따라서 answer+stack.size()가 유효한 괄호문자열을 만들기 위해 필요한 '('와 ')'의 개수이다. 이 방법의 시간복잡도는 O(n), 공간복잡도는 O(n)이다.
문제출처 - https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/