[programmers] 프린터

프로그래머스 Lv.2 프린터

너무 짜증이 나서 포스팅을 해야 겠다. 못 푸는 내 자신이 화가 난다.
정리 해보면 빠트린 부분이 보일까 하여 포스팅 하기로 하였다.

문제 해석

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 
   J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.
중요도와 location이 주어지고, 위 조건에 따라 문서를 인쇄할 때
주어진 location에 있는 문서가 몇 번째로 인쇄되는 지 찾는 문제다.

자꾸만 틀리는 코드

from collections import deque
def solution(priorities, location):
    wait = deque(priorities)
    queue, printed = [], []
    work, idx = 0, 0
    while True:
        work = wait.popleft()
        if len(wait) == 0:
            printed.append(idx)
            break
        else:
            if work >= max(wait):
                printed.append(idx)
            else:
                queue.append(idx)
        idx += 1

    prior = printed + queue

    return prior.index(location) + 1

기본 아이디어

0. deque를 써준 것은 그냥 실행속도를 조금이라도 올리기 위함이었다.
1. 당장 출력할 printed와 대기목록에 넣을 queue 리스트를 셋업한다.
2. 각 문서의 중요도를 담을 work와 그 인덱스를 저장할 idx를 셋업한다.
3. 출력 대기열의 첫 번째 문서의 중요도를 popleft로 꺼낸다.
4. 이때, wait에 남은 문서가 없다면 바로 출력할 문서로 등록한다.
5. 문서가 남아 있다면, 남은 문서 중 가장 우선순위가 높은 것과 비교하여
	5-1) 현재 문서의 중요도가 가장 높다면 즉시 출력한다.
    5-2) 하나라도 더 중요도가 높은 문서가 있다면 대기열에 등록한다.
6. 이 사이클을 반복하기 위해 idx를 더하고 반복문을 계속한다.
7. 반복문이 종료되면 printed 배열에는 즉시 출력한 문서들이 담겨있고,
   queue 배열에는 대기목록으로 미뤄뒀던 문서들이 담겨있다.
8. 이 두 배열을 이어붙이면 해당 index에 있던 문서의 출력 순서가 된다.
9. 이어붙인 배열에서 location의 index에 1을 더해주면 출력 순서이다.

대체 어떤 부분에서 오류가 나는 지 잘 모르겠다.
심지어 상당히 많은 오류가 발생하는 걸 보면, 뭔가 빼먹은 checklist가 있다.

prior 배열을 출력해 보면 원하는 대로 담겨 있는 것 같은데......
어느 부분에서 빠졌을 지 상상이 안 가서 테스트케이스 추가를 못 하겠다 ㅠㅠ

대체 어디서 안 되는 거지???

아놔 ㅡㅡ 문제를 잘못 이해한 것이었다 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

잘못 이해한 부분

중요도가 더 높은 문서가 있으면, 출력 대기열에 바로 추가하는 것이 아니라,
대기목록으로 다시 돌려보내는 것이었다!!!!!!!!!!!!!!!!!!
아니 아무리 생각해도 이상하다 했다. 뭐 이런식으로 출력하나 의심스러웠는데,
문제 이해를 잘못 하고 있었다..

새로 작성한 코드
이해 제대로 했다. 이제 안 될리가 없다.

from collections import deque
def solution(priorities, location):
    for i in range(len(priorities)):
        priorities[i] = [i,priorities[i]]
    todo = deque(priorities)
    printed = []
    while True:
        work = todo.popleft()       # 인덱스와 중요도가 담긴 list를 앞에서부터 뽑아온다.
        if len(todo) == 0:          # 남은 출력 목록이 없다면
            printed.append(work[0]) # work[0]에 담긴 index를 print목록에 추가하고 반복문을 마친다.
            break
        else:
            checker = 0
            for i in todo:              # work[1]에 담긴 중요도를 나머지 목록의 중요도와 체크한다.
                if work[1] >= i[1]:
                    checker += 1
                else:                   # 더 중요한 문서가 있다면 work를 다시 todo의 끝에 밀어넣는다.
                    todo.append(work)
                    break
            if checker == len(todo):    # 지금 문서가 가장 중요한 것이 확실하면,
                printed.append(work[0]) # work[0]에 담긴 index를 print목록에 추가한다.
      
    return printed.index(location) + 1

변경된 아이디어

1. 기본적인 접근 방식은 비슷하지만, 작업 전에 각 문서를 indexing 해준다.
2. indexing한 대기열을 deque형태로 todo에 담아둔다.
3. todo에서 첫 번째 문서를 popleft로 꺼내서 work에 담는다.
	3-1) 문서의 중요도가 남은 것 중 가장 높다면 즉시 출력대기열에 추가한다.
    	 이때 추가할 값은 미리 indexing해뒀던 work[0]을 추가하면 된다!!
    3-2) 그게 아니라면 popleft로 꺼냈던 문서를 다시 대기열(todo)로 돌려보낸다.
4. 이제 올바른 논리대로 출력대기열(printed)에 모든 문서의 index가 담겼다.
5. location의 위치를 printed에서 찾아 1을 더하면 출력 순서가 나온다.

편안하다.
이번 문제는 문제 이해 자체를 잘못 한 케이스였다.
다음에 또 문제를 정확하게 이해하지 않으면, 공허를 헤메게 될 것이다..!