스택(Stack) & 큐(Queue)

스택과 큐는 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조 중 하나로 이 중에서도 스택은 거의 모든 응용 프로그램을 만들 때 사용되는 자료구조이다.

스택은 LIFO(Last In First Out)로 처리되며 접시가 쌓이는 것을 생각하면 쉽게 이해할 수 있다.

큐는 FIFO(First In First Out)로 처리되며 줄을 서서 버스에 타는 것을 생각하면 쉽게 이해할 수 있다.

파이썬은 스택, 큐에 대한 자료형을 따로 제공하지는 않지만 리스트에서 스택과 큐의 연산을 모두 제공한다. 다만 리스트는 동적 배열로 구현되어 있기 때문에 큐의 연산을 수행하는데에 있어 효율적이지는 않다. 큐를 효율적으로 사용하기 위해서는 Deque 자료형을 사용해야 한다. 그러나 굳이 성능을 고려하지 않는다면 스택과 큐 모두 리스트로 처리가 가능하다.

LeetCode 20.Valid Parentheses

괄호로 된 입력값이 올바른지 판별하라.

이 문제는 우선 답을 안보고 스택을 이용해서 먼저 풀어보았다.

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        s_list=list(s)
        while s_list:
            tmp=s_list.pop()
            if tmp==')' or tmp==']' or tmp=='}':
                stack.append(tmp)
            else:
                if not stack:
                    return False
                if tmp=='(':
                    if stack.pop()==')':
                        continue
                    else:
                        return False
                if tmp=='[':
                    if stack.pop()==']':
                        continue
                    else:
                        return False
                if tmp=='{':
                    if stack.pop()=='}':
                        continue
                    else:
                        return False
        if stack:
            return False
        return True

Solution 1 스택 일치 여부 판별

전형적인 스택 문제이다. (괄호를 판별하는 문제는 바로 스택으로 접근하면 된다.) 이 Solution에서는 내가 접근한 방식과 조금은 다르게 (, [, {를 스택에 푸쉬하고 ),],}를 만나면 팝한 결과를 매핑 테이블 결과와 매칭되는지 확인하는 방식으로 해결하였다.

class Solution:
    def isValid(self, s: str) -> bool:
        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이 비어있어야 True가 반환되는 것을 저렇게 표현하여 코드 길이가 줄었다. 실행시간 또한 훨씬 좋았다.

LeetCode 316.Remove Duplicate Letters

중복된 문자를 제외하고 사전식 순서로 나열하라.

Solution 1 재귀를 이용한 분리

우선 문제에 대한 이해가 필요하다. 중복을 제거한 후 사전식으로 정렬하는 것이 아니라 전체 문자열에서 중복을 제거했을 때 최대한 사전식으로 정렬되도록 만드는 문제이다. cbacdcbc를 예로 들어보자.

• 우선 cbacdcbc를 사전순으로 정렬된 집합으로 만들고 이를 순회한다.
• s에서의 집합의 각 원소의 인덱스를 구하여 그 뒤를 접미사로 저장한다.
• s를 집합으로 만든 것과 접미사를 집합으로 만든 것이 같을 경우에는 집합의 다음 원소로 넘어간다.
• 두 집합이 다르다면 접미사에서 현재 원소를 빈칸으로 대체하여 인자로 가지고 재귀호출한다.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        for char in sorted(set(s)):
            suffix=s[s.index(char):]
            if set(s)==set(suffix):
                return char+self.removeDuplicateLetters(suffix.replace(char, ''))
        return ''

재귀함수는 확실히 눈으로만 보면 이해하기 어려운 것 같다.

Solution 2 스택을 이용한 문자 제거

스택을 활용하기 위해서 우선 Counter(s)를 통해 s에 존재하는 원소들의 갯수를 나타내는 딕셔너리를 만들고 스택으로 이용할 리스트를 하나 만들어야 한다. 그리고 현재 문자가 스택에 쌓여있는 문자이고 (이전 문자보다 앞서는 문자) 뒤에 더 존재한다면 (카운터가 0 이상인 경우) 쌓아둔 현재 문자를 꺼내서 지운다. 이는 cbacdcbc에 a가 들어올 때에 이미 c와 b가 제거되어 acdb의 형태를 띄게 된다. 카운터가 0 이상인 c와 b는 뒤에서 다시 붙일 수 있기 때문이다.

if char in seen:
    continue

여기서 seen은 이미 처리된 문자 여부를 확인하기 위해 사용하였다. 이렇게 이미 처리된 문자의 경우에는 스킵하고 넘어간다.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        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)

재귀 풀이 코드가 훨씬 간결하고 이쁘지만 스택 풀이가 더 빠르다.

LeetCode 739.Daily Temperatures

매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라.

Solution 1 스택 값 비교

예제 입력값을 우선 도식화 한다. 그러면 그래프가 하나 그려진다. 현재의 인덱스를 스택에 쌓아두고 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교하여 더 높다면 스택의 값을 팝하고 현재 인덱스와 팝한 인덱스의 차이를 정답으로 처리한다.

while stack and cur>temperatures[stack[-1]]:
    last=stack.pop()
    answer[last]=i-last
stack.append(i)

73, 74, 75, 71, 69, 72, 76, 73으로 시뮬레이션을 돌려보면

• i=0, cur=73. stack=[]
  -> stack=[0]
• i=1, cur=74. stack=[0]. cur>temperatures[stack[-1]]
  -> stack.pop(), answer[0]=1-0=1, stack.append(1)
  -> stack=[1]
• i=2, cur=75. stack=[1]. cur>temperatures[stack[-1]]
  -> stack.pop(), answer[1]=2-1=1, stack.append(2)
• i=3, cur=71. stack=[2]
  -> stack.append(3)
• i=4, cur=69. stack=[2, 3].
  -> stack.append(4)
• i=5, cur=72. stack=[2, 3, 4].
  -> stack.append(5)
  ...

이와 같은 과정을 거치게 된다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer=[0]*len(temperatures)
        stack=[]
        for i, cur in enumerate(temperatures):
            while stack and cur>temperatures[stack[-1]]:
                last=stack.pop()
                answer[last]=i-last
            stack.append(i)
        return answer

To be continue ...