항해99 알고리즘 4회차

2023. 12. 14. 21:12· 항해99
목차
  1. 큐를 이용한 스택 구현 https://leetcode.com/problems/implement-stack-using-queues
  2. 스택을 이용한 큐 구현 https://leetcode.com/problems/implement-queue-using-stacks
  3. 카드2 https://www.acmicpc.net/problem/2164
  4. 프린터 큐 https://www.acmicpc.net/problem/1966

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

 

Implement Stack using Queues - LeetCode

Can you solve this real interview question? Implement Stack using Queues - Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty). Implement the

leetcode.com

문제 접근

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

아쉬운, 놓쳤던 부분

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

맞은 결과

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

Can you solve this real interview question? Implement Queue using Stacks - Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Implement t

leetcode.com

문제 접근

  • 스택 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

Can you solve this real interview question? Design Circular Queue - Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the

leetcode.com

문제 접근

  • 원형 큐로 만들어야하니 포인터 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

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가

www.acmicpc.net

문제 접근

  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 자료구조에

www.acmicpc.net

문제 접근

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

아쉬운, 놓쳤던 부분

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

해답 확인 후 분석

 

이 문서를 인쇄하지 않고 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))
저작자표시 (새창열림)

'항해99' 카테고리의 다른 글

항해99 알고리즘 6회차  (0) 2023.12.19
항해99 알고리즘 5회차  (2) 2023.12.15
항해99 알고리즘 3회차  (0) 2023.12.13
항해99 알고리즘 2회차  (0) 2023.12.12
항해99 알고리즘 1회차  (2) 2023.12.11
  1. 큐를 이용한 스택 구현 https://leetcode.com/problems/implement-stack-using-queues
  2. 스택을 이용한 큐 구현 https://leetcode.com/problems/implement-queue-using-stacks
  3. 카드2 https://www.acmicpc.net/problem/2164
  4. 프린터 큐 https://www.acmicpc.net/problem/1966
'항해99' 카테고리의 다른 글
  • 항해99 알고리즘 6회차
  • 항해99 알고리즘 5회차
  • 항해99 알고리즘 3회차
  • 항해99 알고리즘 2회차
blablax5
blablax5
웹 백엔드취준생 입니다.
blablax5
blablax5
blablax5
전체
오늘
어제
  • 분류 전체보기 (141)
    • 개발 (39)
      • 트러블 슈팅 (25)
      • 서버 & DB (5)
      • 스프링 & 자바 (3)
      • 알고리즘 (6)
    • 스터디 (27)
      • AWS SAA (23)
      • 쉽게 배우는 운영체제 (3)
      • AWS Builders 온라인 시리즈 (1)
    • 학습부채 (0)
    • 항해99 (70)
    • 횡설수설 (3)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • SAA
  • AWS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
blablax5
항해99 알고리즘 4회차
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.