[Programmers] 스택/큐 - 프린터

https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

입출력 예

priorities	location	return
[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

제출 코드

이전에 시도했던 문제인데, 알고리즘에 재미를 붙이기 전이라 정답을 내놓지 못한 문제여서 다시 풀었습니다. 문제를 접근할 때 일단,  두가지 아이디어로 문제를 접근했습니다.

• deque의 popleft를 사용해보자
  • 1번째 요소를 뒤로 shift(이동)시켜줘야하기 때문에 pop이나 popleft와 같은 연산과 append를 사용해야겠다고 생각했습니다.  
  • pop과 popleft는 첫번째 요소를 빼는 상황을 두고 봤을 때 pop은 특정 위치의 원소를 제거할 수 있다는 장점 대신 속도가 O(n)이라는 상대적인 단점이 있습니다. 따라서 첫번째 요소를 제거하고, 속도가 O(1)으로 일정한 popleft를 사용했습니다. 
• location을 통해 answer에 해당하는 원소값을 추출하기 위해서는 주어진 priorities의 index와 value를 저장해줍니다. 
  • 각각의 리스트를 만들어준 후, index의 위치도 함께 변경해줬습니다. 
  • index를 따로 저장해주지 않으면, 여러개의 같은 값의 원소들이 리스트내에 있을때 문제가 발생합니다. list.index()로 특정 원소의 index를 불러올 때 중복값을 가지는 다른 원소가 있으면 가장 앞쪽 원소의 index만 불러오기 때문입니다. 이렇게 되면 위치 정보를 통해 원소에 접근하기 어려워집니다. 
  • 아직 시도하지 않은 점은 value와 index를 각각 리스트로 만들기 보다, dictionary나 리스트와 튜플을 활용한 형태를 사용했으면 좀 더 간결한 코드로 만드는 것입니다. 같은 작업을 각 리스트에 적용하는 방식이라 코드를 읽어가는데 있어서도 가독성이 좋지 않다고 느껴집니다.

from collections import deque

def solution(priorities, location):
    answer = 0
    locations = []

    # priors = priorities
    priors = deque(priorities)
    idx_priors = deque(list(range(len(priors))))
    
    i = 0
    while(1):
        # priorities의 원소가 0개이면 break
        if len(priors) == 0:
            break 

        # print(priors)
        # print(idx_priors)
        
        if priors[i] != max(priors):        # max가 아니면 뒤로 shift
            priors.append(priors.popleft()) # pop은 O(n), popleft는 O(1)
            idx_priors.append(idx_priors.popleft())
        
        else:
            priors.popleft()
            locations.append(idx_priors.popleft())

    # print(f'Final idx: {locations}')

    return locations.index(location)+1
    # return locations.index(location)

if __name__ == '__main__':
    priorities_inputs = [[2,1,3,2], [1,1,9,1,1,1]]  # 1~9로 표현하며 숫자가 클수록 중요하다는 뜻
    location_inputs = [2, 0]                        # 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하
    results = 0 

    results = [solution(priorities_inputs[i], location_inputs[i]) for i in range(len(location_inputs))]
    print(results)

실행 결과 

아직 Big O에 대한 개념이 명확히 안 잡혀서 관련해서는 공부가 더 필요합니다. 단순히 실행결과 시간을 다른 코드와 비교했을 때 시간 효율성이 괜찮은 편에 속했습니다.

테스트 1 〉	통과 (0.18ms, 10.2MB)
테스트 2 〉	통과 (1.16ms, 10.2MB)
테스트 3 〉	통과 (0.82ms, 10.3MB)
테스트 4 〉	통과 (0.15ms, 10.3MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.14ms, 10.3MB)
테스트 7 〉	통과 (0.23ms, 10.3MB)
테스트 8 〉	통과 (0.75ms, 10.3MB)
테스트 9 〉	통과 (0.03ms, 10.2MB)
테스트 10 〉	통과 (0.14ms, 10.2MB)
테스트 11 〉	통과 (0.59ms, 10.2MB)
테스트 12 〉	통과 (0.17ms, 10.2MB)
테스트 13 〉	통과 (0.55ms, 10.2MB)
테스트 14 〉	통과 (0.01ms, 10.3MB)
테스트 15 〉	통과 (0.08ms, 10.3MB)
테스트 16 〉	통과 (0.05ms, 10.2MB)
테스트 17 〉	통과 (1.12ms, 10.2MB)
테스트 18 〉	통과 (0.02ms, 10.3MB)
테스트 19 〉	통과 (0.77ms, 10.3MB)
테스트 20 〉	통과 (0.46ms, 10.2MB)

다른 사람 제출 코드

다른 사람들의 코드를 보는 재미도 있습니다. popleft가 더 빠르다고 알려져서 주로 popleft를 쓸 수 있는 상황엔 다들 쓰는 분위기입니다. 하지만, 제출 코드 중에 pop을 사용하고도 높은 효율성을 보이는 코드가 있어서 공유드립니다. 코드 자체도 굉장히 간결합니다. 

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

실행 결과 

테스트 1 〉	통과 (0.53ms, 10.2MB)
테스트 2 〉	통과 (1.05ms, 10.2MB)
테스트 3 〉	통과 (0.07ms, 10.2MB)
테스트 4 〉	통과 (0.05ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.3MB)
테스트 6 〉	통과 (0.17ms, 10.3MB)
테스트 7 〉	통과 (0.15ms, 10.2MB)
테스트 8 〉	통과 (0.87ms, 10.3MB)
테스트 9 〉	통과 (0.03ms, 10.1MB)
테스트 10 〉	통과 (0.20ms, 10.2MB)
테스트 11 〉	통과 (0.62ms, 10.2MB)
테스트 12 〉	통과 (0.04ms, 10.2MB)
테스트 13 〉	통과 (0.55ms, 10.2MB)
테스트 14 〉	통과 (0.01ms, 10.2MB)
테스트 15 〉	통과 (0.02ms, 10.3MB)
테스트 16 〉	통과 (0.10ms, 10.1MB)
테스트 17 〉	통과 (0.85ms, 10.2MB)
테스트 18 〉	통과 (0.03ms, 10.2MB)
테스트 19 〉	통과 (0.79ms, 10.2MB)
테스트 20 〉	통과 (0.11ms, 10.2MB)

https://github.com/vg-rlo/TIL/blob/master/programmers_printer.py