유효한 괄호 , 중복 문자 제거[스택-(1)]

문제 1 . 유효한 괄호

문제 설명

• 괄호로 된 입력값이 올바른지 판별하라.
• ()[]{} -> 이런 형태가 올바른 형태이다.

풀이

def isValid(s):
    stack = []
    table = {
        ')' :'(',
        '}' :'{',
        ']' :'[',
        
    }
    
    for char in s:
        if char not in table:
            stack.append(char)
        elif not stack or table[char] != stack.pop():
            return False
    return len(stack) == 0

• 파이썬의 리스트는 stack과 큐의 거의 모든 연산을 지원한다.
• 또한 파이썬 리스트는 스택 연산인 push 와 pop이 O(1)에 동작하기 때문에 성능에도 좋은 효율을 가진다.
• 여기서는 ( , [ , { 는 스택에 푸시하고 , ) , ] , }를 만날 때 스택에서 팝한 결과가 매핑 테이블 결과와 매칭되는지 확인하는 것이다.
• 미리 매핑 테이블을 만들어 놓고 테이블에 존재하지 않으면 무조건 푸시하고, 팝했을 때 결과가 일치하지 않으면 False를 리턴하도록 구현했다.

테스트 케이스

-> isValid('()[]')

True

-> isValid('()[]{}')

True

-> isValid('()]}')

False

문제 2. 중복 문자 제거

문제 설명

• 중복된 문자를 제외하고 사전식 순서로 나열하라.
• ex) "bcabc" 로 입력 시, "abc" 로 출력

풀이

import collections
def removeDuplicateLetters(s):
    counter , seen, stack = collections.Counter(s), set(), []
    
    for char in s:
        counter[char] -= 1
        if char in seen:
            continue
        # 뒤에 붙일 문자가 남아 있다면 스택에서 제거
        while stack and char < stack[-1] and counter[stack[-1]] > 0 :
            seen.remove(stack.pop())
        stack.append(char)
        seen.add(char)
        
    return "".join(stack)

• collections.Counter를 통해 주어진 문자열의 원소별 개수를 구할 수 있다.
• seen은 set으로 집합 자료형이고 , 이미 처리된 문자 여부를 확인하기 위해 사용했다. 만일 이미 처리된 문자는 스킵한다.
• 만약 현재 문자 (char)가 스택에 쌓여 있는 이전문자보다 앞선 문자이고, 뒤에 다시 붙일 문자가 남아 있다면, 쌓아둔 걸 꺼내서 없앤다.
• stack[-1]을 통해 가장 최근에 stack에 쌓여 있는 문자를 검색할 수 있다.

테스트 케이스

-> removeDuplicateLetters("cbabc")

"abc"

-> removeDuplicateLetters("cbacdcbc")

"acdb"