LeetCode - Minimum Add to Make Parentheses Valid

문제요약

괄호가 포함된 문자열을 입력받아 해당 문자열을 유효하게 만드는 괄호가 몇개 필요한지 정수를 반환한다

예를 들어, s = "()))" 이면 여는 괄호를 삽입하여 "(()))" 로 만들 거나 닫는 괄호를 삽입하여 "())))"로 만들 수 있다.

예시

1. 입력: s = "())"
   출력: 1
2. 입력: s = "((("
   출력: 3

풀이

var minAddToMakeValid = function(s) {
  let openMark = 0;
  let closeMark = 0;
  for(const c of s){
    if(c === "(") openMark += 1;
    else if(c === ")"){
        if(openMark !== 0){
            openMark -= 1;
        }
        else{
            closeMark +=1;
        }
    }

  }  
  return openMark + closeMark
};

• 여는 괄호를 만날경우 openMark를 1씩 더한다
• 여는 괄호가 앞에 나온경우 닫힌 괄호를 만나면 openMark를 1씩 뺀다
• 여는 괄호가 앞에 나오지 않은 경우 closeMark를 1씩 더한다
• 필요한 여는괄호와 닫힌 괄호의 개수를 더해 반환한다

시간복잡도 : O(n)