[Level 2] 스택/큐. 프린터

 문제 

https://programmers.co.kr/learn/courses/30/lessons/42587?language=python3 

코딩테스트 연습 - 프린터

 사용 언어 

Python3

 풀이 과정 

원래 인덱스를 어떻게 저장해야 하나 백준 24061번 문제를 풀면서도 머리 아프게 고민했던 문제인데...풀다가 풀다가 모르겠길래 구글링해서 힌트만 얻고 내 코드에 넣어 풀 수 있었다.바로 for index, value in enumerate문을 이용하여 원래 인덱스와 값을 묶은 튜플을 원소로 하는 deque를 생성하는 것.여기서는 push와 pop을 자주 사용해야 해서 deque로 만들어줬지만 list도 만들어도 상관없다.

 

그리고 처음에는 맨 앞의 원소를 빼서 맨 뒤로 넘길 때 주석과 같은 코드를 사용했는데 공부하다가 deque에는 rotate()라는 메소드가 있다는 것을 알고 깔끔하게 바꿀 수 있었다.

if request[0][1] != top: # 가장 높은 우선순위 아니면
    #request.append(request.popleft()) # 맨뒤로 보내기
    request.rotate(-1) # 한 칸씩 왼쪽으로 밀기

중간 중간 좀 오래걸린 테스트 케이스도 보이지만 나쁘지 않은 것 같다.

 제출 답안 

from collections import deque

def solution(priorities, location):
    request = deque([(i, v) for i, v in enumerate(priorities)]) # 원래 인덱스와 값을 묶은 튜플을 원소로 하는 deque 생성
    priorities = sorted(priorities, reverse=True) # 내림차순 정렬

    count = 0
    top = priorities[0]
    while len(priorities) != 0:
        if request[0][1] != top: # 가장 높은 우선순위 아니면
            request.rotate(-1) # 한 칸씩 왼쪽으로 밀기
        else: # 가장 높은 우선순위이면
            printed = request.popleft() # 출력
            count += 1 # 번째
            if printed[0] == location: # 내가 요청한 인쇄물이면
                return count # 순서 반환
            else:
                top = priorities[count] # 남은 것 중에 가장 높은 우선순위

 공부한 내용 

deque는 항상 list보다 빠를까?

결론부터 말하자면, queue로 사용하는 경우에만 deque가 list보다 빠르다. 아래 출처 블로그에 따르면 이렇게 나와있다.

deque는 list처럼 [i]와 같은 index에 따른 접근이 불가하기 때문에, 중간에 있는 값에 접근하려면 list를 사용하는 것이 훨씬 효율적인 것이다.

그러나 내가 문제를 풀 때는 deque[index]와 같은 접근이 가능했기에, 이게 무슨말인가 싶어 찾아봤는데 pop(index) 혹은 append(index) 형태는 deque에서 작동하지 않는다. 따라서 값을 중간에 추가하거나 삭제하고 싶을 때는 list를 사용하는 것이 더 효율적이라는 뜻이다.

 

즉 append(), pop()만 사용하는 stack의 경우 list.append()와 deque.append()의 연산 시간에 차이가 별로 없지만

왼쪽의 원소를 넣고 뺄 수 있는 queue의 경우 list.pop(0)와 deque.popleft() 중에는 deque의 연산 시간이 훨씬 빠르다.

list.pop(0)을 상요하게 되면 list의 메모리를 재할당해야 하는 경우들이 생기기 때문이다.

 

따라서 queue 자료형을 사용해야 할 때는 deque를 사용하고, 그렇지 않을 때는 그냥 편한 list를 사용하도록 하자.

 

출처: https://frhyme.github.io/python-lib/python_deque_is_faster_than_lst/

deque의 여러 메소드

deque 확장 (extend, extendleft)

ex = list('good')
# ex = ['g', 'o', 'o', 'd']

dq.extend(ex)
# deque(['p', 'y', 't', 'h', 'o', 'n', 'g', 'o', 'o', 'd'])

dq.extendleft(ex)
# deque(['d', 'o', 'o', 'g', 'p', 'y', 't', 'h', 'o', 'n', 'g', 'o', 'o', 'd'])

- extend(list) : 오른쪽에 주어진 리스트 붙이기

- extendleft(list) : 왼쪽에 주어진 리스트 붙이기, 주어진 리스트는 앞쪽부터 붙기 때문에 거꾸로 들어감

 

deque 제거 (remove, clear)

dq.remove('d')
# deque(['o', 'o', 'g', 'p', 'y', 't', 'h', 'o', 'n', 'g', 'o', 'o', 'd'])

dq.remove('o')
# deque(['o', 'g', 'p', 'y', 't', 'h', 'o', 'n', 'g', 'o', 'o', 'd'])

dq.clear()
# deque([])

- reomove(string) : 제일 처음 나온 해당 string이 제거됨

- clear() : deque 전체 삭제

 

deque 위치 바꾸기 (reverse, rotate)

dq = deque('apple')
dq.reverse()
# deque(['e', 'l', 'p', 'p', 'a'])

dq.rotate()
# deque(['a', 'e', 'l', 'p', 'p'])

dq.rotate(-1)
# deque(['e', 'l', 'p', 'p', 'a'])

dq.rotate(2)
# deque(['p', 'a', 'e', 'l', 'p'])

- reverse() : 말 그대로 뒤집기, 역순으로 바꾸기

- rotate() : 제일 오른쪽에 있는 요소를 맨 왼쪽으로 가져오기 (한 칸씩 오른쪽으로 밀림)

  (rotate(-1)은 왼쪽으로 밀림, roate(n)은 n이 양수일 때 그 수만큼 오른쪽으로 밀림)

 

출처: https://goldory.tistory.com/62

 다른 사람 답안 

프로그래머스는 백준보다 다른 사람들의 코드를 통해 배우기가 편하다.

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

출처: 프로그래머스  

 

파이썬 내장함수 중 any()와 all()이 있다. 둘은 인자로 iterable한 객체를 받는데 이 객체를 돌면서 조건을 검사해 답을 True/False의 답을 반환한다.

• any() : 하나라도 True인게 있으면 True
• all() : 모두 True여야 True 반환

쉽게 생각해 any는 or, all은 and 연산이라 보면 된다.

>>> any([False, False, False])
False
>>> any([False, True, False])
True
>>> all([False, True, False])
False
>>> all([True, True, True])
True

출처: https://otugi.tistory.com/206

 

예전에 공부한 기억이 있는데 이렇게 사용한 걸 보면 항상 신기하다.