[Programmers] Printer.py (stack/queue)

#. Problem

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

* The copyright in this matter is in Programmers

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.

    - 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.

    - 그렇지 않으면 J를 인쇄합니다.

    - 요청한 문서가 몇 번째로 인쇄되는지 return

  3. Create solution plan (select Algorithm, Data structure)

    - queue

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 우선순위가 동일한 작업이 있으므로 작업을 구분

  2. 첫 번째 작업부터 우선순위를 확인하여 더 중요한 작업이 있을 경우 wait list에 append

     더 중요한 작업이 없을 경우 print list에 append

  3. print list와 wait list를 더한 후 해당 작업이 몇 번째에 위치하고 있는지 확인

#. Code

def solution(priorities, location):
    print = []
    works = [(i, pri) for i, pri in enumerate(priorities)]
    while works:
        w = works.pop(0)
        m = max(priorities)
        del priorities[0]
        if w[1] < m:
            works.append(w)
            priorities.append(w[1])
        else:
            print.append(w)
 
    for i, a in enumerate(print):
        if a[0] == location:
            answer = i
    return answer+1

  - (5~12) 작업 목록에서 순서대로 요소를 뽑아 우선순위가 가장 높은 요소와 비교

             뽑은 요소보다 높은 우선순위가 목록에 있을 경우 다시 작업 목록에 append

             그렇지 않을 경우 print list에 append

#. Others code

def solution(p, l):
    ans = 0
    m = max(p)
    # import collections
    # p = collections.deque(p)
 
    while True:
        v = p.pop(0)
        # v = p.popleft()
        if m == v:
            ans += 1
            if l == 0:
                break
            else:
                l -= 1
            m = max(p)
        else:
            p.append(v)
            if l == 0:
                l = len(p)-1
            else:
                l -= 1
    return ans

  - 더 효율적인 시간복잡도를 고려할 경우, dequeue를 사용할 수 있음(#주석)

  - location 값을 조정하면서 요청한 작업의 위치를 확인 -> priorities의 index를 구분할 필요가 없어짐

    (3) 초기 목록에서 가장 우선순위가 높은 작업을 탐색 

    (7~22) priorities list에서 순서대로 pop함수를 사용하여 요소를 추출

             if. 뽑은 요소가 max priority와 같을 경우, 

                순번을 1 늘려주고

                여기서 location가 0일 경우 요청한 문서를 찾았으므로 반복문을 종료, 

                그렇지 않을 경우 location에서 1을 감소시켜주고, priorities list에서 새로운 max priority를 탐색

          else. 뽑은 요소가 max priority와 같지 않을 경우,

                 priorities list에 요소를 다시 append

                 여기서 location이 0일 경우, 요소가 list의 맨 뒤로 이동하었으므로  location 값을 priorities 크기 -1로 변경

                 그렇지 않을 경우 location에서 1을 감소

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

  - 내가 짠 코드와 비슷하지만 더 간결한 코드