일일온도, 스택 구현, 큐 구현, 원형 큐 디자인 [스택,큐-(2)]

문제 1. 일일온도

문제설명

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

• ex) 입력 T = [73,74,75,71,69,72,76,73] -> 출력: [1,1,4,2,1,1,0,0]

스택을 이용한 풀이

def dailyTemp(T):
    answer = [0] * len(T)
    stack = []
    for i, cur in enumerate(T):
        # 현재 온도가 스택 값보다 높다면 현재 인덱스 - stack 인덱스
        while stack and cur > T[stack[-1]]:
            last = stack.pop()
            answer[last] = i - last
        stack.append(i)
    
    return answer

• 현재의 인덱스를 계속 스택에 쌓고, 이전보다 상승하는 지점이 나타난다면 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교해서 더 높다면 기존 스택의 값은 팝으로 꺼내고 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다.
• while stack : 은 stack 리스트 안에 값이 하나라도 있을 경우 참이 된다.

문제 2. 큐를 이용한 스택 구현

큐

• 큐는 FIFO(선입선출) 로 처리되는 상대적으로 스택에 비해서는 쓰임새가 적은 자료구조이다. 하지만 데크나, 우선순위 큐, 너비 우선 탐색(BFS) 등 널리 쓰인다.
• 파이썬의 리스트는 큐의 모든 연산을 지원한다.
• 데크는 좀 더 나은 성능을 가지고, 양방향 삽입 삭제가 모두 가능하다.

문제 설명

큐를 이용해 다음 연산을 지원하는 스택을 구현하라.

• push(x) : 요소 x를 스택에 삽입한다.
• pop() : 스택의 첫 번째 요소를 삭제한다.
• top() : 스택의 첫 번째 요소를 가져온다.
• empty(): 스택이 비어 있는지 여부를 리턴한다.

풀이

class MyStack:
    def __init__(self):
        self.q = collections.deque()
        
    def push(self,x):
        self.q.append(x)
        # 요소 삽입 후 맨 앞에 두는 상태로 재정렬
        for _ in range(len(self.q) - 1) :
            self.q.append(self.q.popleft())
            
        def pop(self):
            return self.q.popleft()
        
        def top(self):
            return self.q[0]
        
        def empty(self):
            return len(selq.q) == 0

• push의 경우를 제외하면 간단한 코드이다.
• push는 맨 뒤에 요소를 삽입 후 , 삽입한 값을 맨 앞으로 두기 위해서 삽입한 값을 제외한 모든 값을 popleft()를 통해서 맨 뒤로 한 개씩 붙이는 작업을 추가한다.

문제 3. 스택을 이용한 큐 구현

문제 설명

스택을 이용해 다음 연산을 지원하는 큐를 구현하라.

• push(x) : 요소 x를 큐 마지막에 삽입한다.
• pop() : 큐의 첫 번째 요소를 제거한다.
• peek() : 큐의 첫 번째 요소를 조회한다.
• empty(): 큐가 비어 있는지 여부를 리턴한다.

스택 2개 사용하여 풀이

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []
        
    def push(self,x):
        self.input.append(x)
    
    def pop(self):
        self.peek()
        return self.output.pop()
    
    def peek(self):
        #output이 없으면 모두 재입력
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]
    
    def empty(self):
        return self.input == [] and self.output == []

• peek과 pop은 같은 데이터를 불러오기 때문에, pop을 구현할 때 peek을 통해 데이터를 불러오고 pop으로 제거하는 알고리즘이다.
• peek의 경우에는 output 리스트가 비어있으면 input리스트에 있는 값들을 전부 역순으로 output에 입력하고, output 리스트의 마지막 값을 리턴한다. ( 즉, input 값의 첫번째 값을 return 한다. )

문제 4. 원형 큐 디자인

문제 설명

원형 큐를 디자인하라.

• 원형 큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하다. 그러나 마지막 위치가 시작 위치와 연결되는 원형 구조를 가진다.
• 링 버퍼(Ring Buffer) 라고도 한다.
• 동작하는 원리는 투 포인터와 비슷하다. 기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없지만, 원형 큐는 앞쪽에 공간이 남아있다면 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용이 가능한 구조이다.

풀이

class MyCircularQueue:
    def __init__(self,k):
        self.q = [None] * k
        self.p1 = 0
        self.p2 = 0
        
    # enQueue(): rear포인터 이동
    def enQueue(self, value) :
        if selq.q[self.p2] is None:
            self.q[self.p2] = value
            self.p2 = (self.p2 + 1) % self.maxlen
            return True
        else:
            return False
        
    # deQueue(): front 포인터 이동
    def deQueue(self):
        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):
        return -1 if self.q[self.p1] is None else self.q[self.p1]
    
    def Rear(self):
        return -1 if self.q[self.p2 - 1 ] is None else self.q[self.p2 - 1]
    
    def isEmpty(self):
        return self.p1 == self.p2 and self.q[self.p1] is None
    
    def isFull(self):
        return self.p1 == self.p2 and self.q[self.p1] is not None

• 초기화시 큐의 크기k를 입력받고, 최대 길이인 maxlen으로 지정한다. p1 은 front의 포인터, p2는 rear의 포인터로 초기값은 0으로 지정했다.
• enQueue를 통해 rear 포인터를 이동시킨다. 해당 포인터가 가리키는 지점의 값이 None이면 value를 넣고 포인터를 앞으로 이동한다. ( maxlen 의 값을 넘는 걸 방지하기 위해 maxlen의 나머지 값으로 포인터 값일 지정해준다. 그리고 비정상적인 경우에는 False 를 리턴한다.
• deQueue의 경우에는 enQueue와는 같은 방식이지만 넣는 값을 반대로 진행하면 된다. ( front 포인터를 움직여 값을 비우는 작업이기 때문이다.)
• Front() , Rear() 연산은 해당 포인터 지점의 값을 가져오는 연산이다. 그러므로, Front()는 첫 번째 요소를 조회하는 연산이다.
• isEmpty() 와 isFull() 은 큐가 비었는지, 혹은 가득 채워져 있는지 조회하는 연산이다.