문제 설명
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
- 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
- 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
- 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
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풀이
아이디어
제한사항에서 priorities의 길이가 100이 최대이기 때문에 사실 스택/큐 순서대로 구현하면서 풀 수 있다. 하지만 규칙성이 있기 때문에 더 시간 복잡도가 적은 풀이를 찾을 수 있겠다는 생각이 들어서 처음에는 다른 방식으로 접근했다.
예시가 매우 적기 때문에 [5,1,"2",4,2,5] 라는 새로운 예시로 생각해보자.
이때 "2"가 출력되는 위치를 찾아보면,
처음에 5가 꺼내지고, [1,"2",4,2,5]
다음에 1,"2",4,2가 뒤로 밀리고, [5,1,"2",4,2]
다음에 5가 꺼내지고, [1,"2",4,2]
그리고 1,2가 밀리고 [4,2,1,"2"]
다음 4가 꺼내지고, [2,1,"2"]가 되고 2가 꺼내지고,
다음으로 "2"가 꺼내진다.
따라서 2가 꺼내지는 순서는 5번째가 된다.
나의 이해
되게 복잡해보이지만, 나는 이 과정을 어떻게 파악했냐면,
- 결국 나보다 우선순위가 높은 애들은 나보다 '먼저' 나간다.
=> 따라서 나보다 우선순위가 높은 애들의 개수를 세서 count에 더한다.- 나머지 중 나와 우선순위가 같은 애들만 고려하면 된다. 우선순위가 낮은 애들은 나보다 늦게 나가기 때문이다.
=> 따라서 나보다 우선순위 높은 애들을 처리할 때, 누가 마지막으로 처리되는지 그 인덱스를 저장한다. 이때, 마지막으로 처리되는 애의 인덱스는 나보다 큰 값중 가장 작은 값이 된다. 그 마지막 처리된 애를 기준으로 나와 같은 값들끼리 순서를 정해준다.
예를들어 [5,1,"2",4,2,5] 라고 해보면, 2보다 큰 4,5의 개수를 센다. 그러면 5가 2개, 4가 1개로 총 3개다. 그리고 나와 같은 2와의 순서만 결정해주면 된다.
이때, "나보다 큰 값중 가장 작은 값"이 마지막 처리되는 인덱스다. 이게 무슨말이냐면, 5가 가장 먼저 2개 다 나가고, 2보다 크지만 2보다 큰 값들 중 5보다 작은 4라는 값이 가장 마지막으로 나갈 것이다. 따라서 4의 인덱스를 기준으로 오른쪽에 있는 2가 먼저 처리되고, 그 다음에 "2"가 처리된다. 따라서 4개가 먼저 나가고 해당 값은 5번째로 나가게 된다!!
그걸 구현한 코드가 아래와 같다.
def solution(priorities, location):
count = 0
target = priorities[location]
last_max = 9
last_idx = target + 1
for i in range(len(priorities)) :
# 나보다 큰 것 중 가장 작은 값 인덱스
if priorities[i] > target :
count += 1
if last_max >= priorities[i] :
last_max = priorities[i]
last_idx = i
for j in range(last_idx,len(priorities)) :
if priorities[j] == target :
if j == location :
break
else :
count += 1
if last_idx > location :
for k in range(last_idx) :
if priorities[k] == target :
if k == location :
break
else :
count += 1
return count+1
하지만...
자꾸 통과를 못했다! 한 45-60점 사이를 왔다갔다 했다.
알고보니 엣지케이스가 있었다...!!
아래 링크에 질문하신분이 나랑 비슷한 접근을 하셨는데,
https://school.programmers.co.kr/questions/35085
[2,3,3,"2",9,3,3], 3, return = 6
이 경우가 반례가 된다.
2보다 크고 큰 애들중에 작은 값이 3으로 여러개다. 이때, 이 3들이 실행되는 순서가 9에 의존하기 때문에 위와 같은 예시로는 동작을 안한다.
자세히 살펴보자면, 내 로직으로는 for문을 앞에서부터 돌기 때문에 마지막으로 저장되는 인덱스가 마지막 3을 가리키는 [6]이 된다. 따라서 앞선 2가 먼저 큐를 나오고, "2"가 그 다음으로 출력되는 것으로 return이 7이된다.
하지만 실제로는 9,3,3 => 3,3,2 이런 순서로 출력되어 return이 6이 되어야 한다.
다시 푼 풀이
그래서 얌전히 스택 큐로 다시 풀었다. ㅎㅎ
사실 시간초과가 안나면 스택/큐로 풀어도 충분하다!!
어쩌다보니 아래 풀이도 일반적이진 않은가 싶지만...
priorities를 deque로 만들고,
priorities의 원소를 꺼내면서 location을 하나 앞으로 당겨준다.
이렇게 해야 하는 이유는 원소를 꺼내면 내가 목표로 하는 location의 인덱스가 바뀌기 때문이다.
그리고 all 문법을 사용해 현재 priorities의 있는 모든 원소보다 top이 이상일 때, 그니까 최댓값일때 지금 꺼낸 값이 내가 꺼내려던 값(loaction == -1)이라면 answer+1를 출력한다. 몇 번째로 출력되는지를 구해야 하기 때문에 앞선 pop된 개수+1을 해준다.
내가 원하는 타겟 값은 아니지만 배열 중 최댓값이면 꺼낸 것의 개수만 세준다. (answer+=1)
그리고 최댓값이 아니라면 다시 뒤로 append해주는데, 이때 내가 꺼낸 값이 location이었다면 인덱스를 바꿔줘야 하므로 location을 다시 맨 뒷 인덱스로 지정해준다.
from collections import deque
def solution(priorities, location):
curr_idx = 0
answer = 0
priorities = deque(priorities)
while priorities :
top = priorities.popleft()
location -= 1
if all(top>= num for num in priorities) :
if location == -1 :
return answer + 1
else :
answer +=1
else :
priorities.append(top)
if location == -1 :
location = len(priorities) - 1
return answer
느낀점
문제에서 주어진 조건에 알맞는 풀이를 고르는 것이 매우 중요하겠다!
처음 푼 풀이처럼 시간을 줄이려고 하는 시도는 좋았으나 해당 문제 조건은 스택/큐를 활용해도 충분했기 때문에 굳이 그렇게 돌아갈 필요가 없었다!! ㅎㅎ
