[알고리즘] 프로그래머스 - 프로세스

문제

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

프로그래머스

 

풀이

정말 그냥 문제에 나와있는대로 하면 된다.

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

 

큐니까 선입된(가장 왼쪽) 프로세스를 꺼내고, 다시 큐에 넣을땐 맨 오른쪽으로 넣어주면 된다.

옛날에 풀었던 적이 있는 문제인데, 그 당시에 프로세스를 뺀 다음 실행 대기 큐에서 가장 우선순위가 높은 프로세스를 찾을 때 sorted함수를 썼어서 그런지 시간복잡도는 예전 코드가 더 높더라. 아이디어는 고만고만하지만 ㅠ 지금 다시 푼게 시간복잡도가 더 낮아져서 기분이 좋았다... 

 

정답 코드

이번 풀이 

from collections import deque
def solution(priorities, location):
    answer = 1
    priorities = [(idx,value) for idx,value in enumerate(priorities)]
    q = deque(priorities)
    
    while q:
        idx,item = q.popleft()
        if not q:
            return answer
        max_num = max([i[1] for i in q])
        
        if item < max_num:
            q.append((idx,item))
            
        else:
            if idx == location:
                break
            else:
                answer += 1
        
    return answer

 

저번 풀이

from collections import deque
def solution(priorities, location):
    answer = 0
    priorities = deque([(i,v) for i,v in enumerate(priorities)])
    cnt=0
    # print(priorities)
    
    while len(priorities)>0:
        tmp_pri=sorted(priorities,reverse=True, key=lambda x : x[1])
        if priorities[0][1] != tmp_pri[0][1]:
            tmp_num=priorities.popleft()
            priorities.append(tmp_num)
        else:
            tmp_num=priorities.popleft()
            cnt+=1
            if tmp_num[0]==location:
                return cnt
        # print(priorities)
            

    
    return answer