항해99 알고리즘 4회차

큐를 이용한 스택 구현 https://leetcode.com/problems/implement-stack-using-queues

Implement Stack using Queues - LeetCode

문제 접근

• 왼쪽으로 추가하고, 왼쪽으로 삭제
• 파이썬에서 메소드를 지원해서 바로 해결 하였다.

아쉬운, 놓쳤던 부분

• 스택과 큐에 대해 아직 응용 할 수 없다고 많이 느끼고있다.

맞은 결과

class MyStack:

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

    def push(self, x: int) -> None:
        self.stack.appendleft(x)

    def pop(self) -> int:
        return self.stack.popleft()

    def top(self) -> int:
        return self.stack[0]

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

 

맞은 결과 - 파이썬 알고리즘 인터뷰

class MyStack:

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

    def push(self, x: int) -> None:
        self.stack.append(x)

        for i in range(len(self.stack) - 1):
            self.stack.append(self.stack.popleft())
            # 2 1 3
            # 1 3 2
            # 3 2 1

    def pop(self) -> int:
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

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

---

스택을 이용한 큐 구현 https://leetcode.com/problems/implement-queue-using-stacks

Implement Queue using Stacks - LeetCode

문제 접근

• 스택 2개를 이용해서 큐를 만들어라고 했다.
• 생각이 안나서 책의 내용을 확인 하고 이해하고 짰다.
  • input, ouput 스택을 2개가 있으면
  • input = [1,2,3]에서 pop을 하면 3부터 나오니 이걸 이용하여 output에 넣어준다.
  • output = [3,2,1]로 들어가니 1로 정상적으로 큐 형식으로 된다.
  • peek에서 output에 값을 넣어주는 과정을 하고 pop을 한다.

아쉬운, 놓쳤던 부분

• 두번째 코드에서 push를 할 때 반복문으로 정렬을 할려고 했지만 안돼서 책의 해답을 확인 하였다. 전부 다 지우면서 popleft의 값을 append 하는게 맞았다.

맞은 결과 - 파이썬 알고리즘 인터뷰

class MyQueue:

    # input에 차례대로 1,2,3
    # output에 다시 3,2,1을 넣어주고
    # output을 꺼낸다.

    def __init__(self):
        self.input = []
        self.output = []

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        self.peek()
        return self.output.pop()

    def peek(self) -> int:
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())

        return self.output[-1]

    def empty(self) -> bool:
        return len(self.input) == 0 and len(self.output) == 0

---

원형 큐 디자인 https://leetcode.com/problems/design-circular-queue

Design Circular Queue - LeetCode

문제 접근

• 원형 큐로 만들어야하니 포인터 2개 만들어서 진행을 할려고 했다. front쪽 포인터가 움직여야 하는걸 인지를 못했다. 그래서 당연히 테스트케이스만 통과를 하고 제출은 실패했다

아쉬운, 놓쳤던 부분

• 원형 큐를 제대로 이해하지 못하고 무작정 작성을 한게 문제였던것 같다.
• 이해하고 끝까지 가면 시간을 너무 잡아먹기 때문에 일단 해답을 보는식으로 하는 방향으로 가긴 가야한다.

틀린 결과

class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = collections.deque()
        self.front = 0
        self.rear = 0
        self.size = k

    def enQueue(self, value: int) -> bool:
        if self.rear < self.size:
            self.rear += 1
            self.queue.appendleft(value)
            return True
        return False

    def deQueue(self) -> bool:
        if len(self.queue) != 0:
            self.rear -= 1
            self.queue.popleft()
            return True
        return False

    def Front(self) -> int:
        return self.queue[0]

    def Rear(self) -> int:
        return self.queue[0]

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

    def isFull(self) -> bool:
        return self.rear == self.size

 

해답 확인 후 분석

 

책을 읽고 원형 큐의 원리를 파악을 먼저 하였다. front, rear는 별개로 보는 느낌으로 진행

rear 값을 호출 할 때 왜 -1을 해주지 ?

• front, rear는 같은 위치
• 추가 시 rear는 한칸 앞으로
• 그렇기에 rear의 값을 가져올땐 -1을 해줘야함

왜 삽입, 삭제 할때 % 연산자가 사용 됐지 ?

• 나머지값이 그 다음 인덱스로 떨어지고
• 최대값이 되면 0으로 초기화

책에서는 공백 한칸으로 무조건 남겨두는데 어떻게 == 사용하지 ?

• 값을 끝까지 채웠을때는 모든 공간을 사용한다.
• 그래서 front,rear의 위치가 같다.

맞은 결과 - 파이썬 알고리즘 인터뷰

class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = [None] * k
        self.front = 0
        self.rear = 0
        self.size = k

    def enQueue(self, value: int) -> bool:
        if self.queue[self.rear] is None:
            self.queue[self.rear] = value
            self.rear = (self.rear + 1) % self.size
            return True
        else:
            return False

    def deQueue(self) -> bool:
        if self.queue[self.front] is None:
            return False
        else:
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.size
            return True

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

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

    def isEmpty(self) -> bool:
        return self.front == self.rear and self.queue[self.front] is None

    def isFull(self) -> bool:
        return self.front == self.rear and self.queue[self.front] is not None

---

카드2 https://www.acmicpc.net/problem/2164

2164번: 카드2

문제 접근

1. 1234를 0번째를 없애는것
2. 2를 맨 뒤에 보낼 것
3. 반복
4. 마지막에 남은 값

맞은 결과

import collections

N = input()
queue = collections.deque(i+1 for i in range(int(N)))

while len(queue) > 1:
    queue.popleft()
    queue.append(queue.popleft())

print(int(queue[0]))

---

프린터 큐 https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

문제 접근

• 문제는 이해를 했는데 입력, 출력 부분은 아무리 읽어도 이해가 안갔다. 다음에는 좀 더 꼼꼼히 읽어봐야겠다.

아쉬운, 놓쳤던 부분

• 결국 해답을 보면서 문제를 봤는데, 이해가 너무 안가서 전체적으로 문제가 많다 해답을 보면서 파이썬 문법을 아직 이해 못한게 많다고 느꼈다.

해답 확인 후 분석

 

이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다.

1. i, rank = dq.popleft()
2. if rank == index[-1] 아닐 경우
3. dq.append((i, rank))

정렬된 index와 dq를 비교를 하는 원인이 뭘까?

• dq = [(0,1)]
• if rank == index[-1]:

맞은 결과 - 출처(벨로그)

from collections import deque

test_case = 1  # 찾을려는 문서 총 개수

for _ in range(test_case):
    dq = deque()
    n, m = map(int, "6 0".split())  # 문서 개수, 찾을려는 위치
    index = list(map(int, "1 1 9 1 1 1".split()))  # 문서

    for i, rank in enumerate(index):  # index, value 반복
        dq.append((i, rank))  # dq에 [index, value] 추가

    index.sort()  # 정렬
    count = 0

    while dq:
        i, rank = dq.popleft()  # i에 인덱스, rank에 중요도를 담는다.

				# dq에서 꺼낸 첫번째 값과 index의 마지막 값이 같은지
        if rank == index[-1]:
            index.pop()
            count += 1

            # 인덱스와 찾을려는 인덱스가 같으면 끝
            if i == m:
                print(count)
                break
        else:
            dq.append((i, rank))