[코딩연습] Minimum Add to Make Parentheses Valid 유효한 괄호 만들기

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을 해주자. 

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();
    }
}

answer는 필요한 '('의 개수이고 stack에 들어있는 '('만큼 ')'도 필요하다. 따라서 answer+stack.size()가 유효한 괄호문자열을 만들기 위해 필요한 '('와 ')'의 개수이다. 이 방법의 시간복잡도는 O(n), 공간복잡도는 O(n)이다.

문제출처 - https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/