1966 프린터 큐, Programmers 프로세스

💡문제 분석 요약

• Queue에서 조금 바꿔서 우선순위를 보고 pop 여부를 결정한다.
• 우선순위가 낮은데 앞에 있다면 맨 뒤로 돌아가게 되고, 자신이 제일 높은 우선순위라면 pop된다.

💡알고리즘 설계

• 딕셔너리, 우선순위큐 등을 살펴보았다.
• 딕셔너리로 우선순위와 index를 매칭시켜볼까도 생각했는데, index 업데이트 하는 게 매우 번거로울 것 같아서 그만두었다.
• 그리고 우선순위큐를 보았는데 아직은 잘 다루지 못하겠어서 제쳐두었다. 이는 나중에 다시 포스팅해야겠다.

💡코드

from collections import deque

for _ in range(int(input())):
    n, m = map(int, input().split())
    files = deque(list(map(int, input().split())))
    ans = 1

    """ 첫번째 원소가 max보다 작다면 어차피 뒤로 가야해서 m == 0을 체크하지 않음. """

    while len(files) > 0: # 덱 내에 인쇄할 파일이 남아있을 때까지
        if files[0] < max(files): # 첫번째 원소가 max가 아니면 맨 뒤로 보냄(= pop 후 append)
            files.append(files.popleft())

        else: # 첫번째 원소가 max 이상일 때
            if m == 0: # m=0 즉 첫번째 원소를 찾고 있던 거라면 바로 break 종료
                break
            files.popleft() # max 이상이면 바로 pop해도 됨
            ans += 1

        # 여기까지 내려왔으면 결과적으로 1개가 pop되든, 맨 뒤로 가든 했으니까 index를 하나씩 땡김
        if m > 0: #
            m -= 1
        else: # 맨 앞이었다면 index를 맨 뒤로 보냄
            m = len(files) - 1
    print(ans)

💡시간복잡도

• 원래같으면 pop과 append에서 O(N)이었겠지만 이는 덱을 이용했기 때문에 O(1)만에 할 수 있고 따라서 파일 개수만 보면 되기 때문에 O(N)이 되지 않을까 싶다.

💡 틀린 이유

• 인덱스 업데이트 하는 부분에서 많이 틀렸다. 모든 인덱스를 업데이트 하려고 했었는데 사실은 내가 보고싶은 파일은 하나기 때문에 그럴 필요가 없었고, 그래서 m 하나만 비교해도 되는 것이었다.

💡 틀린 부분 수정 or 다른 풀이

• enumerate를 이용한 풀이를 여럿 보았는데, 아직 이 문법을 잘 몰라서 추후 정리해보아야겠다.

 

07/14일 추가)) 같은 문제인 Programmers의 프로세스 문제를 풀었다.

from collections import deque

def solution(priorities, location):
    ans = 0
    priorities = deque(priorities)

    while priorities:  # 안에 있는 값이 다 사라질 때 까지
        if priorities[0] >= max(priorities): # 맨 앞이 최대면 pop
            priorities.popleft()
            ans += 1
            if location == 0:
                break
        else: # 맨 앞이 최대가 아닌 일반적인 경우
            priorities.append(priorities.popleft())

        """ pop 할 때에도 location 값을 줄여줘야하므로 공통되는 부분은 if-else 밖으로 뺌. (처음에 이거 안해서 틀림) """
        location -= 1

        if location < 0: # 음수일 때 location 값 보정
            location = len(priorities) - 1

    return ans

print(solution([2, 1, 3, 2], 2)) # 답 1
print(solution([1, 1, 9, 1, 1, 1], 0)) # 답 5

💡 느낀점 or 기억할정보

• enumerate 문법 정리
• heapq, Priorityqueue 관련 정리하기
• if-else 공통되는 부분은 모아서 밖으로 빼도 되는 것 생각