2023. 5. 9. 20:37ㆍComputer Science/Algorithm
프로세스 파이썬 풀이
문제설명
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
- 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
- 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
- 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
- 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 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… 과 같이 표현합니다.
접근 방법
문제를 읽고나서, 가장 먼저 max_priority value를 이용해, priorities 덱을 돌면서 현재 큐에 대기중인 프로세스를 꺼내고(popleft) 우선순위를 비교해 반환하면서 location index에 위치하는 원소의 실행 순서를 찾아내는 방식을 생각했다.
1차 작성 코드
from collections import deque
def solution(priorities, location):
q = deque(priorities)
answer = 0
while q:
m = max(q)
l = q.popleft()
location -= 1
if l != m:
q.append(l)
if location < 0:
location = len(q) -1
else:
answer += 1
if location < 0:
break
return answer
처음 시도한 코드는 다음과 같이 돌아가도록 생각하며 작성했다.
1. priorities가 배열로 주어지므로, deque로 만든다.
2. location에 위치하는 프로세스를 처리하기 위해 큐를 반복문 안에서 처리해보자
3. 큐 안에서 가장 높은 우선순위가 몇인지m
변수에 저장한다.
4. q에서 가장 앞에 위치하는 프로세스를l
변수에 저장한다.
5. 변수`l`
에 저장하면서popleft()
했으므로, 타겟 프로세스의 위치가 1 줄어들었다. 고로 location--;
6. if문 부터 보자. 가장 앞 프로세스가 max_priority의 프로세스가 아니라면 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있는 것이므로 다시 큐에 프로세스를 넣는다.else문은 가장 앞 프로세스가 가장 높은 우선순위를 가지므로 실행한다.
7. 우선순위 프로세스를 실행했으므로 다른 순위의 프로세스는 큐에 대기중인 순서대로 실행한다.
정리해보면 이 문제에서 중요한 것은 두가지라 할 수 있다.
1. 현재 타겟 로케이션의 프로세스가 어디에 위치해있는지 파악할 것
2. 큐에서 꺼낸 프로세스를 실행하는 조건을 적절히 설정할 것
다른 풀이로 로직 갈아 엎기
다른 사람의 풀이 보기로, 가장 많은 사람들이 제출하고 따봉을 많이 받은 풀이를 가져와보았다.
다른 풀이 코드
def solution(priorities, location):
queue = [(i,p) for i,p in enumerate(priorities)]
answer = 0
while True:
cur = queue.pop(0)
if any(cur[1] < q[1] for q in queue):
queue.append(cur)
else:
answer += 1
if cur[0] == location:
return answer
가장 눈에 띄는 점은 우선 우선순위가 주어지는 순서인i
와 proirities의 원소p
로 enumerate를 사용해 queue를 구현했다.
그 다음으로, 반복문 내 조건문에서 any
를 이용해 튜플에서 우선순위가 들어있는 원소를 비교한 건데, 여기서 any
에 대해 잠깐 알아보자.
Python의 any() 함수
파이썬에서 any()
함수는 list의 원소를 필터링하거나 조건 검사할 때 사용하는 함수이다.
예를들어 test_list라는 이름의 리스트가 있다 해보자.
# Python3 code to demonstrate working of
# Check if any element in list satisfies a condition
# Using list comprehension
# initializing list
test_list = [4, 5, 8, 9, 10, 17]
# Check if any element in list satisfies a condition
# Using list comprehension
res = True in (ele > 10 for ele in test_list)
# Printing result
print("Does any element satisfy specified condition ? : " + str(res))
# Output
# Does any element satisfy specified condition ? : True
파이썬에서는 res = True in (ele > 10 for ele in test_list)
라는 코드에서 볼 수 있듯이 리스트 내에서 원소를 지정해 조건을 만족하는지 검색할 수 있다. 위 코드는 n이 리스트의 길이라 할 때, O(n)의 시간복잡도를 가진다.
True in (...) :
(...) 안에 쓰인 조건문으로 리스트를 검사한다. 조건을 만족하는 어떤 한 원소라도 존재한다면 True를 반환한다.ele > 10 for ele in test_list
: 리스트 검사 조건으로, 리스트 내부의 원소들이 10보다 큰지 검사한다.
이번에는 파이썬의 내장함수인 any()
함수를 사용하는 예제를 살펴보자. 이 함수는, 위 코드 예제처럼 리스트 내의 모든 원소를 검사하며, O(n)의 시간복잡도와 O(1)의 공간복잡도를 가진다. 또, 어떤 원소든 리스트 내의 조건을 만족하는 원소가 있는지 그 여부에 따라 True 혹은 False를 리턴한다.
# Check if any element in list satisfies a condition
# Using any()
res = any(ele > 10 for ele in test_list)
# Printing result
print("Does any element satisfy specified condition ? : " + str(res))
# Output
# Does any element satisfy specified condition ? : True
즉, 위에서 배운 any()
내장함수를 이용해서 if any(cur[1] < q[1] for q in queue)
라는 조건문으로 queue안의 모든 튜플들을 순회하면서 순회중인 튜플의 우선순위가 현재 프로세스에서 pop한 cur 튜플의 우선순위보다 큰지 확인하고, 조건을 만족하면 queue에 현재 프로세스를 다시 집어 넣는 방식으로 로직을 구현할 수 있다.
그리고 큐 안에 원소를 튜플로 집어넣었으므로, 조건을 만족하지 않는다면 실행 순번에 해당하는 answer를 증가시키고 간단하게 cur[0]
이 타겟 프로세스 위치인지 검사하는 조건만 넣으면 답을 얻어낼 수 있다.
TIL
- 내장함수 any()와 next()와 기본 문법으로 리스트를 검사하는 방법을 복습하자
- enumerator의 사용법에 익숙해지자.
++ 유사한 문제는 백준의 자료구조 (스택,큐,덱) 문제집에서 모아볼 수 있다.
'Computer Science > Algorithm' 카테고리의 다른 글
[힙] 프로그래머스 이중우선순위큐 파이썬 풀이 (0) | 2023.05.09 |
---|---|
[스택/큐] 프로그래머스 올바른 괄호 - 파이썬 (0) | 2023.04.14 |
[스택/큐] 프로그래머스 기능개발 - 파이썬 (0) | 2023.04.14 |
허프만 알고리즘으로 문자열 압축하기, Huffman Algorithm Encoding (0) | 2022.04.16 |
[알고리즘을 위한 수학이론] 유클리드 호제법을 PS에 적용하기 -1 (Ft. C++) (0) | 2022.02.28 |