[프로그래머스] 프린터

[문제]

 

코딩테스트 연습 - 프린터

 

 

---

 

[풀이]

처음 문제를 접하고 우선순위라는 키워드 때문에 priority queue를 사용하는 문제일 것으로 생각했으나, 요구사항을 확인한 결과 항상 최선의 priority를 찾아 pop 하는 priority queue와는 다른 동작이 필요했다. 문제의 요구사항을 정리해보면 다음과 같다.

 

while queue가 비어있지 않을 동안
  if queue[0]가 가장 우선순위가 높은 출력물이면 then
      queue[0]를 popleft한다.
      카운터를 1 증가 시킨다.
      if pop 한 출력물 = 출력 순서를 알고자 하는 출력물 then
          출력 카운트를 반환한다.
  else then
      queue에서 가장 높은 우선순위 요소 전까지 순차적으로 popleft한 출력물을 
      그대로 queue에 append한다.
      가장 높은 우선순위 출력물을 pop한다.
      출력 카운트를 1 증가 시킨다.
      if pop 한 출력물 = 출력 순서를 알고자 하는 출력물 then
          출력 카운트를 반환한다.

 

입력으로 priority와 location이 주어졌으므로 각 priority마다 location이 존재해야 한다고 판단했다. 따라서 priorities 데이터를 가지고 (priority, location) 형태로 만들어 놓고 시작했다.

 

최초 풀이에는 첫번 째 인덱스 요소를 제외하고 나머지 인덱스 요소를 리스트로 변환한 뒤에 내림차순으로 정렬해서 max value를 구해보고자 했다. 이 과정에서 python 내장 함수를 사용했는데, 기본 정렬로 했을 때 한 가지 문제가 있었다. 만약 [동일한 우선순위의 출력 작업이 여러 개 존재하는 경우 그 안에서 두 번째 인덱스인 location 순서로 정렬이 되어버리기 때문에 주어진 priorities의 순서가 지켜지지 않는다. 즉 다시 말해 priorities = [1, 2, 2, 2]와 같이 주어진 경우 1보다 높은 우선순위인 2를 가진 요소들이 인덱스 1 ~ 3까지 존재하는데, 의도한 대로라면 다음 인덱스 데이터에 해당하는 (2, 1)이 max value가 되어야 하나 더 뒤에 위치한 (2, 3)이 max value가 되어버린다.

 

따라서 queue에서 0번 인덱스의 값을 현재 값으로 잡고 1 ~ 마지막 인덱스 까지의 요소들 선형 탐색하면서 현재 값보다 큰 경우가 있는지 찾아 없으면 popleft 하고 출력 카운트를 1 증가시키고, 있다면 pop 한 결과를 다시 append 하도록 하는 것이었다. 이 과정을 반복하면서 출력 순서를 알고자 했던 출력물이 pop 되는 경우의 출력 카운트를 리턴하면 정답을 도출할 수 있을 것으로 생각했다. (성능상의 이유로 선형 탐색 대신 내장 정렬 함수를 사용하기 원한다면 key argument에 람다식을 지정하거나 cmp_to_key를 통해 comparator를 지정해야 한다.)

 

위의 내용을 바탕으로 구현해본 코드는 다음과 같다.

from collections import deque


def solution(priorities, location):
    queue = deque()
    for i in range(len(priorities)):
        queue.append((priorities[i], i))

    deque_cnt = 0
    while queue:
        max_elem = queue[0]
        for i in range(1, len(queue)):
            if max_elem[0] < queue[i][0]:
                max_elem = queue[i]

        if max_elem[0] > queue[0][0]:
            for i in range(len(queue)):
                if queue[0][0] < max_elem[0]:
                    queue.append(queue.popleft())
                else:
                    elem = queue.popleft()
                    deque_cnt += 1
                    break
        else:
            elem = queue.popleft()
            deque_cnt += 1
        
        if elem[1] == location:
            return deque_cnt

 

 

---

 

[개선]

1. range()를 사용하여 인덱싱을 하는 대신 enumerate()를 사용하여 (index, value)의 튜플 자료형으로 구성된 deque를 만든다.
2. deque의 첫번 째 요소를 popleft()하여 그 값과  deque에 남은 나머지 값들을에 대해 any()를 사용하면 첫 번째 요소의 priority 보다 더 높은 priority의 요소가 있는지 확인할 수 있다. 만약 첫 번째 요소의 priority보다 높은 요소가 있는 경우 pop 한 데이터를 다시 deque에 넣어준다. 그렇지 않으면 출력하고 출력 카운트를 증가시킨다. 이때 location이 일치하면 현재 출력 카운트를 리턴한다.

def solution(priorities, location):
    # (locaion, priority) 형태의 튜플을 만들어 queue에 넣어준다.
    queue = deque([(i, p) for i, p in enumerate(priorities)])
    answer = 0
    while queue:
        # 출력할 원소를 queue에서 꺼낸다.
        p_data = queue.popleft()
        # 큐 내부 원소 가운데 출력할 원소보다 우선순위가 높은 것이 있으면...
        if any(p_data[1] < q_data[1] for q_data in queue):
            # 출력하지 않고 queue에 다시 넣어준다.
            queue.append(p_data)
        # 출력이 진행된 경우
        else:
            # 출력 순서 카온터를 증가 시키고
            answer += 1
            # 출력된 건의 location이 지정한 location과 일치하는 경우
            if p_data[0] == location:
                # 출력 순서를 return 한다.
                return answer