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

문제설명

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

 

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.

2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.

3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.

  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

 

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

 

제한사항

priorities의 길이는 1 이상 100 이하입니다.

priorities의 원소는 1 이상 9 이하의 정수입니다.

priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.

location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.

priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

입출력 예

priorities	location	return
[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

입출력 예 설명

예제 #1

 

문제에 나온 예와 같습니다.

 

예제 #2

 

6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.

 

문제 해결 방법

 

문제 해결 방법은 코드 주석에 녹였다. 

코드 구현

def solution(priorities, location):
    answer = 0
    
    # 우선 순위대로 몇번이 먼저 실행될지는 priority Queue로 매김 - 1번 llist 리스트 생성
    
    # location을 통해 초기의 priorities list에서 해당 자리의 원소 찾기 -> 출력
    
    llist=[]
    max_qsize = len(priorities)
    
    for i in range(max_qsize):
        llist.append(0)
    
    # 큐 전체에서 우선순위 젤 높은걸 찾아서 위치를 기록 후 삭제함. 단, front랑 rear 움직이지 않음
    # 큐 전체에서 우선순위 젤 높은걸 원소 값을 찾아서 해당 원소값을 아까전에 위치 기록한 지점부터 찾아서 순위 매김 
    
    # 원소가 뽑혔으면 priorities의 원소는 0으로 변경
    
    cnt = 1
    
    while 1:
        if cnt-1 == len(priorities):
            break
        
        if cnt == 1:
        	# king은 priorities에서 가장 큰 값이다 (우선순위 최고)
            king = max(priorities)
            # king의 위치 확인 
            # cnt가 1일 때는 이렇게 진행 
            front = priorities.index(king)
            llist[front] = cnt # 1 = cnt, 루프를 돌 때 마다 1씩 증가함
            priorities[front] = 0 
            front+=1
            cnt+=1
            if front == max_qsize:
                    front = 0
        else:
            # cnt가 2 이상이면 아래의 로직을 진행
            king = max(priorities)
            if priorities[front] == king :
                llist[front] = cnt
                priorities[front] = 0
                front+=1
                cnt+=1
                if front == max_qsize:
                    front=0
            else:
                front+=1
                if front == max_qsize:
                    front = 0
                
    answer = llist[location]
        
    return answer

 

시간/공간 복잡도

O(N)이 되겠다. 

 

최적화 및 개선

하지않음

어려웠던 점

 

이 문제를 풀면서 배열이나 리스트가 선형인게 아니라 원형이였으면 참 좋겠다 이런 생각을 계속 했었다. 

생각만 하고 구현할 줄을 몰랐다. 

그래서 '원형큐' 라는 말을 예전에 어디서 들어본거 같아서 찾아봤다. 

내가 구현할 문제는 이렇게까지 구현할 필요는 없을것 같은데,,, 

그냥 리스트를 원형으로만 만드는게 필요했기 때문이다. 

게다가 priorities의 원소도 1부터 9까지라 빼고 넣고 할 필요도 없고 해서도 안됐다.

0으로 이미 우선순위를 기록한 수 임을 표시할 수 있었다. 

 

원형큐 개념을 살펴보다가 내가 어떤 원소를 가리키고 있는지에 대한 변수를 만들고 

그 변수가 해당 리스트를 순환하며 조회하게끔 구현하기만 하면 됐었다. 

근데 그게 어려웠는데 해보니까 별거아니네 ㅠ;;

왜 레벨 2 문제인지 이제 알 것 같다.

 

괜히 쫄았다. 쫄면 더 간단히 생각할 수 있는것도 어렵게 생각하는것 같다. 

 

쫄지마!!!!!