[algorithm] 백준 18258 - 큐 2

[algorithm] 백준 18258 - 큐 2

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 18258번 문제 - 큐 2 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 18258

 

백준 18258번 큐 2 문제 보러가기

 

반응형

 

문제 해석

 

우리가 알고 있는 큐의 기능을 구현하는 문제입니다.

제한 사항은 연산당 시간복잡도가 O(1) 이여야 한다는 점입니다.

리스트를 사용해서 큐를 구현하고 pop을 했을 때 모든 요소들의 인덱스가 바뀌는 게 되는데

그러면 pop 연산의 시간복잡도가 O(n)이 되어버립니다.

이를 해결한 풀이를 아래에서 살펴보시죠.

 

풀이

 

# 18258 큐 2

import sys
from collections import deque

n = int(sys.stdin.readline())

q = deque([])

for _ in range(n):
    cmd = sys.stdin.readline().split()
    if cmd[0] == 'push':
        q.append(cmd[1])
        
    elif cmd[0] == 'pop':
        if len(q) == 0:
            print(-1)
        else:
            print(q.popleft())
            
    elif cmd[0] == 'size':
        print(len(q))
        
    elif cmd[0] == 'empty':
        if len(q) == 0:
            print(1)
        else:
            print(0)
            
    elif cmd[0] == 'front':
        if len(q) == 0:
            print(-1)
        else:
            print(q[0])
            
    elif cmd[0] == 'back':
        if len(q) == 0:
            print(-1)
        else:
            print(q[-1])

 

풀이 해석 및 팁

 

큐의 기능을 구현하기 위해서 리스트를 사용할 수도 있지만 collections의 deque를 사용해 보았습니다.

pop의 경우에 리스트의 요소를 제거해주어야 하는데 del()을 사용해서 요소를 제거하면

삭제한 요소보다 뒤에 있는 요소들의 인덱스가 모두 변경되는 과정이 생깁니다.

그 과정으로 인해 시간초과라는 결과를 맛보게 될 것입니다.

그렇다면 리스트를 사용해서 풀 수가 없느냐...?

실제로 리스트의 요소를 삭제하지 않고 pop에 적용될 인덱스를 따로 관리해 주면 리스트를 사용해서

풀이가 가능합니다.

---

여기까지 백준 18258번 큐 2 문제 풀이였습니다.

이번 문제의 정답률은 32% 정도입니다.

 

큐의 기능을 직접 구현하는 문제로 시간복잡도만 신경 써준다면 쉽게 해결 가능한 문제였습니다.

 

궁금하신 점은 댓글로 남겨주시기 바랍니다.

 

감사합니다.