[프로그래머스] 프로세스

문제 : 

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

 

코드: 

1. 우선 순위가 동일한 경우도 있기 때문에 추후 location을 찾기 위해 (우선 순위, 처음 위치) 형태로 큐 생성

2. 가장 앞에 있는 프로세스를 꺼내 현재 값 보다 우선 순위가 높은 프로세스가 있는지 확인

  2-1. 있다면 다시 뒤로 보냄

  2-2. 없다면 answer 을 증가 시키고 (몇 번째 실행 하는지 알기 위해)

3. 내가 찾는 위치가 맞다면 answer 반환

from collections import deque
def solution(priorities, location):
    answer = 0
    # (우선순위, 처음 위치) 형태로 큐 생성
    queue = deque([(p,i) for i,p in enumerate(priorities)])
    
    while queue:
    	# 가장 앞에 있는 프로세스 꺼냄
        current = queue.popleft()
        # 큐에 현재 값 보다 우선순위가 높은 프로세스가 있는지 확인
        if any(current[0] < q[0] for q in queue):
            queue.append(current) # 있다면 다시 뒤로 보냄 
        else:
            answer+=1 
            if current[1] == location: # 내가 찾는 위치 (location)이 맞다면 반환
                return answer

 

 

고민했던 부분

1. max() vs any() 

• max(queue) : 큐 안에 있는 모든 요소들을 끝까지 훑어야만 결론을 내릴 수 있음
• any(current < q for q in queue): 검사하다가 나보다 큰 값이 하나라도 발견된다면 검사를 중단하고 True 반환

 

2. deque 사용

• 라스트 pop(0) : 맨 앞을 빼면 , 뒤에 줄 서 있던 데이터들이 전부 한 칸씩 앞으로 땡겨져야 함 (시간 복잡도 O(N))
• poplfet() : 양방향 연결 리스트 형태라 앞뒤 끝단에서 빼는 건 그냥 연결만 끊으면 됨 (시간 복잡도 O(1))

   * 데이터가 100개라면 리스트는 100번 움직이지만, deque 는 한 번의 동작으로 끝남 

 

---

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42587