[릿코드] Minimum Add to Make Parentheses Valis

문제

릿코드 921. Minimum Add to Make Parentheses Valis

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

 

코드

class Solution(object):
    def minAddToMakeValid(self, s):
        s = deque(s)

        stack = []
        item = s.popleft()
        stack.append(item)

        while s:
            item = s.popleft()

            if not stack:
                stack.append(item)
            else:
                if item == ')' and stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(item)    

        return len(stack)

 

풀이

s = deque(s)

s의 글자들을 왼쪽부터 하나씩 꺼낼것이기 때문에 s를 큐 형태로 바꾼다.

 

stack = []
item = s.popleft()
stack.append(item)

스택 배열의 초기화 작업을 한다.

스택을 하나 생성하고, s의 왼쪽에서 글자를 하나 떼서(=popleft() 해서) 스택에 넣어준다.

 

while s:

s에서 원소들을 하나씩 떼서 스택에 넣어주는 작업을 할것이다.

그래서 s에 원소가 없을때까지 다음의 작업을 반복한다.

 

if not stack:
    stack.append(item)
else:
    if item == ')' and stack[-1] == '(':
        stack.pop()
    else:
        stack.append(item)

s의 왼쪽 원소를 하나 떼서 item 변수에 초기화한다.

 

만약 stack에 원소가 들어있지 않다면

item을 stack에 추가한다.

 

stack에 원소가 들어있다면

스택의 맨 마지막 원소가 '('이고 item이 ')'여서 괄호가 짝을 짓는다면, stack의 마지막 원소를 pop한다.

괄호가 짝짓지 않는다면 stackdp item을 추가한다.

 

return len(stack)

스택에는 짝을 짓지 못한 괄호만 남아있을것이다. 그리고 괄호들은 모두 '('이거나 ')' 둘 중 하나일것이다.

stack에 남아있는 괄호의 수 만큼 그에 대응하는 괄호를 추가하면 모든 괄호가 짝이 지어진다.

ex 1 ) stack에 남아있는 괄호들 = ['(', '('] ➡️ 추가해야하는 괄호 = ')', ')'

ex 2 ) stack에 남아있는 괄호들 = [')', ')', ')', ')', ')', ')'] ➡️ 추가해야하는 괄호 = '(', '(', '(', '(', '(', '('

 

따라서 스택에 남아있는 아직 짝지어지지 못한 괄호의 숫자가 문제의 정답일것이다.

 

다른 코드

class Solution(object):
    def minAddToMakeValid(self, s):
        return abs(s.count('(') - s.count(')'))

 

⬇️위의 코드를 바탕으로 해쉬를 이용한 코드

class Solution(object):
    def minAddToMakeValid(self, s):
        dic = {'(': 0, ')': 0}

        for letter in s:
            if letter == '(':
                dic['('] += 1
            else:
                dic[')'] += 1

        return abs(dic['('] - dic[')'])

 

풀이

스택/큐 개념을 사용하지 않았다.

return abs(s.count('(') - s.count(')'))

문제의 조건 중 "In one move, you can insert a parenthesis at any position of the string" 이라는 조건이 있다.

문자열의 아무 위치에나 괄호를 넣을 수 있다는 뜻이다.

 

그래서 짝지어지는 '('와 ')'를 빼고 남는 괄호의 수를 반환하면 정답이 나온다.

 

이 코드의 시간 복잡도는 O(2n)이다.

count()가 O(n)의 시간 복잡도를 가지기 때문에

s.count('(') ➡️ O(n)

s.count(')') ➡️ O(n)

둘이 합해서 O(2n)이다.

 

해시 태이블을 사용해서 count()를 쓰지 않고 원소의 수를 세면 O(2n)에서 O(n)으로 줄일 수 있겠다고 생각했다.

그래서 해시를 이용하여 코드를 다시 짜봤다.

 

dic = {'(': 0, ')': 0}

'('의 개수는 0,

')'의 개수도 0 으로 초기화한다.

 

for letter in s:
    if letter == '(':
        dic['('] += 1
    else:
        dic[')'] += 1

s문자열을 한글자씩 돌아가면서

해당 글자가 '('이면 dic['(']의 밸류를 1 증가시키고

해당 글자가 ')'이면 dic['(']의 밸류를 1 증가시킨다.

 

return abs(dic['('] - dic[')'])

짝지어지는 '('와 ')'를 빼고 남는 괄호의 수를 반환한다.

 

새롭게 배운점 / 느낀점

• 실제로는 count()활용 함수보다 해시 활용 함수가 시간이 2ms 더 걸렸다. count() 활용 코드는 O(2n)이고, 해시 활용 코드는 O(n)인데 왜 해시 활용 코드가 더 시간이 오래 걸릴까? 이유는 파이썬의 인터프리터(파이썬 코드를 실행하는 프로그램)와 메모리 접근법의 차이 때문이다.
  • 파이썬 인터프리터는 내장함수(count() 등)에 대해 최적화를 많이 수행한다.
  • 반면에 해시로 작성된 코드에서는 내가 정의한 논리로 반복문을 수행하기 때문에 파이썬 인터프리터가 최적화 할 수 있는 부분이 상대적으로 적다.
  • count()를 사용한 코드에서는 메모리 접근 패턴이 단순하다. 단순히 문자열을 2번 순회한다.
  • 반면에 해시를 사용한 코드에서는 문자열을 순회하면서 딕셔너리에도 접근한다. 이는 약간의 메모리 접근 오버헤드를 추가할 수 있다.
• 하지만 주어지는 문자열의 길이가 길어진다면 해시를 이용한 코드가 더 유리하다. (실제 성능은 구현된 환경 및 파이썬 인터프리터의 최적화 상태에 따라 다를 수 있다.)

# 성능 테스트 코드

import time

class Use_count(object):
    def minAddToMakeValid(self, s):
        return abs(s.count('(') - s.count(')'))

class Use_hash(object):
    def minAddToMakeValid(self, s):
        dic = {'(': 0, ')': 0}
        for letter in s:
            if letter == '(':
                dic['('] += 1
            else:
                dic[')'] += 1
        return abs(dic['('] - dic[')'])

# input_string = "문자열 넣으시오~~"

# count 썼을때 실행 시간 측정
use_count = Use_count()
start_time = time.time()
use_count.minAddToMakeValid(input_string)
print("count 썼을때 실행 시간:", time.time() - start_time)

# 해시 썼을때 실행 시간 측정
use_hash = Use_hash()
start_time = time.time()
use_hash.minAddToMakeValid(input_string)
print("해시 썼을때 실행 시간:", time.time() - start_time)

 

 

• 프로그래머스 <올바른 괄호> 문제와 비슷하다고 느꼈다. (올바른 괄호 TIL : https://hyein6604444.tistory.com/22)

 

 

 

다른 의견이나 궁금하신게 있다면 편하게 댓글 달아주세요 :)