문제 개요
큐(queue)의 앞(front), 중간(middle), 뒤(back) 세 위치에서 모두 값을 삽입(push)하고 삭제(pop)할 수 있는 자료구조를 구현해야 한다고 가정해 보겠습니다.
세 가지 위치 각각에 대해 삽입 함수와 삭제 함수를 한 쌍씩 만들고, 추가로 현재 큐의 전체 상태를 확인할 수 있는 함수도 함께 구현합니다.
입력 예시
push_from_back(10)
push_from_back(20)
push_from_front(30)
push_from_middle(40)
push_from_front(50)
show_queue()
pop_from_back()
show_queue()
pop_from_front()
show_queue()
pop_from_middle()
show_queue()
출력 결과
[50, 30, 40, 10, 20]
[50, 30, 40, 10]
[30, 40, 10]
[30, 10]
해결 접근 방법
이 문제는 내부적으로 리스트(array)를 사용해 큐를 표현하면 간단하게 해결할 수 있습니다. 각 연산은 다음과 같이 정의됩니다.
- push_from_front(value): 값을 배열의 인덱스 0 위치에 삽입합니다.
- push_from_middle(value): 값을 배열 길이를 2로 나눈 몫(len // 2) 위치에 삽입합니다.
- push_from_back(value): 값을 배열의 맨 끝에 추가합니다.
- pop_from_front(): 배열이 비어 있지 않다면 첫 번째 요소를 삭제하고 반환합니다.
- pop_from_middle(): (배열 길이 − 1)을 2로 나눈 몫 위치의 요소를 삭제하고 반환합니다.
- pop_from_back(): 배열의 마지막 요소를 삭제하고 반환합니다.
- show_queue(): 별도의 입력 없이 현재 배열 전체를 그대로 반환합니다.
여기서 주목할 점은 중간 위치 계산 방식입니다. 삽입 시에는 len // 2를 사용하지만, 삭제 시에는 (len - 1) // 2를 사용합니다. 이 차이 덕분에 요소 개수가 홀수일 때 중간 요소가 일관되게 처리됩니다.
구현 예제
아래는 위 로직을 파이썬 클래스로 구현한 전체 코드입니다.
class Solution():
def __init__(self):
self.array = []
def push_from_front(self, value):
self.array.insert(0, value)
def push_from_middle(self, value):
self.array.insert(len(self.array) // 2, value)
def push_from_back(self, value):
self.array.append(value)
def pop_from_front(self):
return (self.array or [-1]).pop(0)
def pop_from_middle(self):
return (self.array or [-1]).pop((len(self.array) - 1) // 2)
def pop_from_back(self):
return (self.array or [-1]).pop()
def show_queue(self):
return self.array
ob = Solution()
ob.push_from_back(10)
ob.push_from_back(20)
ob.push_from_front(30)
ob.push_from_middle(40)
ob.push_from_front(50)
print(ob.show_queue())
ob.pop_from_back()
print(ob.show_queue())
ob.pop_from_front()
print(ob.show_queue())
ob.pop_from_middle()
print(ob.show_queue())실행 결과
[50, 30, 40, 10, 20]
[50, 30, 40, 10]
[30, 40, 10]
[30, 10]
코드 설명
(self.array or [-1]) 패턴은 배열이 비어 있을 때를 대비한 안전장치입니다. 빈 리스트는 파이썬에서 거짓(False)으로 평가되므로, 배열이 비어 있으면 [-1] 리스트가 대신 사용되어 -1을 반환함으로써 인덱스 오류(IndexError)를 방지합니다.
또한 insert(0, value)와 pop(0)은 리스트의 모든 요소를 한 칸씩 이동시켜야 하므로 O(n)의 시간 복잡도를 가집니다. 성능이 중요한 환경이라면 양방향 연결리스트 기반의 collections.deque를 활용하는 것이 더 효율적인 대안이 될 수 있습니다.