99클럽 코테 스터디 5일차 TIL [04/04]

[시작]

참여 기간 : 2025/03/31 ~ 2025/04/28

참여 난이도 : 파이썬 / 비기너

⏳ 코테 스터디 진행도 🧱 : [▰▰▰▰▰▰▰▰░                                         ] 5/29일 (17%)

본 글에서 다룬 문제 : leetcode(Implement Stack using Queues)

문제 푸는 데 걸린 시간 : 28분 37초

 

 

 

[오늘의 문제]

어제 풀었던 문제의 반대

이번에는 큐를 이용해서 스택을 구현하는 듯

 

 

 

[문제 분석]

내가 볼 때 큐로 스택을 구현하는 방법은 크게 2가지다.

큐 2개를 사용하거나 큐 1개로만 구현하거나

일단 1개로만 구현을 해보고 시간복잡도나 코드 가독성 이런 게 생각보다 별로라면

2개로 구현해보는걸로 결정했다.

 

 

 

[의사 코드]

x를 새로 넣을 때(push) 한번 큐에 넣은 뒤에

기존에 있던 애들을 앞에서 빼서 뒤로 붙이는 과정을 반복하면

새로 들어온 x가 맨앞에 오게 됨

그러면 큐의 front가 곧 스택의 top이 된다

이러면 회전으로 큐만 써서 스택을 구현가능하다.

 

 

 

[의사 코드를 실제 코드로 구현]

from collections import deque

class MyStack:
    def __init__(self):
        self.queue = deque()
        
    def push(self, x: int) -> None:
        self.queue.append(x)
        for i in range(len(self.queue) - 1):
            front = self.queue[0]
            self.queue.popleft()
            self.queue.append(front)

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

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

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


        


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

★ 코드 설명 ★

일단 양쪽에서 빠르게 삽입/삭제가 가능한 큐인 deque을 사용했고

의사 코드에서도 말했다시피

x를 큐의 뒤에 추가한 뒤에

큐에 들어있던 친구들을 앞에서 빼서 다시 뒤에 붙이는 작업을 반복함

이걸 반복하면 x가 맨 앞에 오게 됨

큐의 맨 앞 = 스택의 탑

스택의 pop()은 가장 최근에 넣은 x을 꺼내야 하니까

큐의 맨 앞에서 popleft() (이미 push시 회전으로 맨 앞에 와있음)

그리고 스택의 top은 가장 위에 있으니까 self.queue[0]로 확인가능함

empty(self)부분은 큐가 비어있으면 스택도 비어있으니 True

하나라도 있으면 False

말로 길게 쓰니까 두서가 없는데 요약하면 다음과 같음

 

메서드	동작은 어떻게?	큐에서 어떻게 처리?
push(x)	x를 스택 위에 넣음	뒤에 넣고 앞쪽을 돌려서 x가 맨 앞에 오도록 회전
pop()	스택 위에서 제거	큐 맨 앞 꺼냄
top()	스택 위를 확인	큐 맨 앞 확인
empty()	비었는지 확인	큐의 길이가 0인지 확인

 

 

 

[제출 결과]

 

 

 

[실수한 부분]

• 회전 과정에서 횟수 계산 실수
  • x를 맨 앞 위치로 가져오기 위해서 (현재 큐 크기 - 1) 회만큼 회전해야 하는데 계산 실수로 맨 앞에 오지 않음
  • LIFO 순서가 어긋나서 최종 결과가 잘못됨
• pop()에서 회전을 또 시켰음
  • LIFO 순서가 또 깨짐
  • 나는 큐 하나만 사용해서 원래 큐의 맨 앞을 그냥 popleft() 하는 것만으로 충분했는데 추가 회전을 시켜버림
  • 의도치 않은 다른 결과가 나왔음

 

 

 

 

[마무리]

수면 부족인 상태로 문제 풀려고 하니까 숟가락으로 땅 파는 느낌이었다...

싱싱한 머리로 문제를 풀 수 있는 컨디션을 유지하자