yongchanchun

yongchanchun

I’m trying to post on a daily basis
this may be hard but Nothing is achieved without trying!

스택, 큐

5 minute read

Question 20: Linked List Cycle

괄호로 된 입력값이 올바른지 판단하라 입력: (){}[]

출력: true

풀이 1: 스택 일치 여부 판별

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

중요 내용

  1. stack 변수에 append 와 pop을 반복해나가는 알고리즘이다. 이렇게 리스트에 값을 추가하며 값을 제거해 나가는 알고리즘은 자주 쓰이는 방법이므로 꼭 숙지하도록 하자!

Question 21: 중복 문자 제거

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

입력: ‘cbacdcbc’

출력: ‘acdb’

사전식 순서는 다음과 같은 규칙이 있는 것을 발견하였다.

  1. 문자열을 앞에서부터 차례로 문자를 서로 비교한다.
  2. 문자가 문자열에서 한개 나타나면 해당 문자는 그대로 둔다.
  3. 문자가 문자열에서 여러개 나타나고 바로 뒤에 있는 문자보다 작으면 그대로 둔다.

풀이 1: 재귀를 이용한 분리

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 ''

중요 내용

  • 다음과 같은 순서로 재귀 구조가 실행된다.
    1. 문자열에서 중복된 문자를 제거하고 알파벳 순서로 정렬한다.
    2. 정렬한 문자 순서대로 반복문을 돈다.
    3. 접미사(suffix)는 iterator 로부터 슬라이싱한 값이다.
    4. set(문자열)=set(suffix) 이면 suffix를 분리하고 iterator를 공백으로 만든다.
    5. removeDuplicateLetters 함수에 suffix를 인수로 넣음으로써 1~4의 과정을 반복한다.

풀이 2: 스택을 이용한 문자 제거

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 stack:
                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)

기억해야 할 함수

  1. collections.Counter(string): 문자열에서 각 문자가 나온 횟수만큼을 딕셔너리로 만들어 리턴한다.

중요 내용

  1. 이 방법 또한 처음에는 이해하기 매우 어려웠으나 다음과 같은 규칙을 찾으니 이해하기 한결 수월해졌다.
    • 문자가 s에 하나밖에 없는 경우에는 stack에 그대로 둔다.
    • 만약 다음 iterator가 stack의 제일 마지막의 문자보다 작고 그 문자가 s에 한개 이상 존재하면 그 문자를 지우고 iterator를 append 한다. 이 때, 반복문은 while문을 씀으로써 iterator와 stack의 제일 마지막의 문자와 비교하는 것을 반복한다.

Question 22: 일일 온도

온도를 입력받은 후 더 따뜻한 날씨를 위해서 몇일을 기다려야 하는가?

입력: T = [73,74,75,71,69,72,76,73]

출력: [1,1,4,2,1,1,0,0]

내 풀이

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        for i,tmp in enumerate(temperatures):
            for j,tmp2 in enumerate(temperatures[i+1:]):
                if tmp2 > tmp:
                    stack.append(j+1)
                    break
                if j==len(temperatures[i+1:])-1:
                    stack.append(0)
                    
            if i==(len(temperatures)-2):
                break
                
        stack.append(0)
        return stack
  • 브루트 포스 방법을 이용하여 깔끔하지 않은 방법으로 풀었다.
  • 예외처리가 많이 필요한 방법이여서 좋은 방법은 아니다.

결과

타임에러가 떴다.

풀이 1: 스택 값 비교

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

중요 내용

  1. days 변수에 temperatures의 요소의 갯수만큼 0을 사전에 부여한 후 반복문을 돌며 나중에 바꾸는 방법이다.
  2. 기존 풀이 방법과는 다르게 stack에 요소의 값이 아닌 인덱스 값을 저장하였다.
  3. stack, pop, while문을 이용하여 만들어낼 수 있는 알고리즘을 생각하자!

Question 23: 큐를 이용한 스택 구현

큐를 이용해 스택을 구현하라

입력: stack.push(1)

입력: stack.push(2)

입력: stack.pop()

출력: 2

내 풀이

파이썬의 큐에 대해 아는 것이 거의 없어서 결국 풀지 못하였다.

풀이 1: push() 할 때 큐를 이용해 재정렬

class MyStack:

    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
            
    def pop(self) -> int:
        return self.q.popleft()
        
    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0

중요 내용

  1. 파이썬에서의 큐의 구현은 데크(deque)를 이용한다.
  2. 데크는 사용할 수 있는 함수가 append, popleft 이므로 이 두개의 함수를 이용해 스택을 구현해야 한다.

Question 24: 스택을 이용한 큐 구현

스택을 이용해 큐를 구현하라

입력: stack.push(1)

입력: stack.push(2)

입력: stack.pop()

출력: 1

내 풀이

결국 풀지 못하였다.

풀이 1: 스택 2개 사용

class MyQueue:

    def __init__(self):
        self.stack = []
        self.q = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        
    def pop(self) -> int:
        self.peek()
        return self.q.pop()
    
    def peek(self) -> int:
        if not self.q:
            while self.stack:
                self.q.append(self.stack.pop())
        return self.q[-1]

    def empty(self) -> bool:
        return (len(self.stack) + len(self.q)) == 0

중요 내용

  1. 큐를 이용해 스택을 구현할 때의 풀이와는 다르게 pop과 append를 한번에 같이 사용하면 삭제했다가 추가하는 과정을 무한 반복하기 때문에 이 방법은 사용할 수 없다.
  2. 클래스 안의 함수에서 같은 클래스 안의 다른 함수를 구현할 때 다른 함수의 return 문은 값을 반환하는데 사용된다.

Question 25: 원형 큐 디자인 (재풀이)

원형 큐를 디자인하라

입력:
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(3);
myCircularQueue.enQueue(4);
myCircularQueue.Rear();

myCircularQueue.isFull();

myCircularQueue.deQueue();
myCircularQueue.isEmpty();

출력: True
True
4
False
True
False

내 풀이

class MyCircularQueue:

    def __init__(self, k: int):
        self.q = []
        self.k = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        else:
            self.q.append(value)
            return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return -False
        else:
            self.q.pop(0)
            return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.q[0]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.q[-1]

    def isEmpty(self) -> bool:
        return len(self.q) == 0

    def isFull(self) -> bool:
        return len(self.q) == self.k

결과

Runtime: 85 ms, faster than 50.03% of Python3 online submissions for Design Circular Queue. Memory Usage: 14.5 MB, less than 96.23% of Python3 online submissions for Design Circular Queue

  • 이 문제는 난이도가 별 두개인 것이 이해가 되지 않을 정도로 쉽게 풀었다.
  • 큐의 모양이 원형이라는 특징을 살리지 않은 풀이 방법이여서 다소 변칙적인 풀이 방법이라고 할 수 있다.

풀이 1: 값만 변경

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [None] * k
        self.maxlen = k
        self.p1 = 0
        self.p2 = 0

    # enQueue(): 리어 포인터 이동
    def enQueue(self, value: int) -> bool:
        if self.q[self.p2] is None:
            self.q[self.p2] = value
            self.p2 = (self.p2 + 1) % self.maxlen
            return True
        else:
            return False

    # deQueue(): 프론트 포인터 이동
    def deQueue(self) -> bool:
        if self.q[self.p1] is None:
            return False
        else:
            self.q[self.p1] = None
            self.p1 = (self.p1 + 1) % self.maxlen
            return True

    def Front(self) -> int:
        return -1 if self.q[self.p1] is None else self.q[self.p1]

    def Rear(self) -> int:
        return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]

    def isEmpty(self) -> bool:
        return self.p1 == self.p2 and self.q[self.p1] is None

    def isFull(self) -> bool:
        return self.p1 == self.p2 and self.q[self.p1] is not None

기억해야 할 함수

  1. 표현식 if 가정문 else 표현식: if, else문을 한 줄로 풀어서 쓸 수 있다.

중요 내용

  1. 투 포인터 방법을 이용한 풀이 방법이다. front는 제일 앞의 값에 위치한 포인터이고, rear은 제일 뒤에 위치한 포인터이다.
  2. 값을 추가하면 rear 포인터가 추가한 값으로 이동하고 값을 삭제하면 front 포인터가 삭제한 값 다음으로 넘어간다.

Comments

You May Also Enjoy

특별한 파이썬 함수

less than 1 minute read

파이썬에는 복잡한 과정을 단순화 시켜주는 특별한 함수들이 많이 존재한다. 이러한 함수들을 정리해보았다.