99클럽 코테 스터디 28일차 TIL (프로세스) - 프로그래머스

말하는 감자·2024년 8월 18일

99클럽 99클럽 3기 programmers python queue 자료구조 코딩테스트 코딩테스트 준비 큐 파이썬 향해99

99클럽 3기

목록 보기

28/42

어제 벨로그에 큐에 관한 내용을 포스팅했는데, 때마침 오늘 문제가 큐 자료구조를 활용한 문제이네요.

배운것들을 잘 활용해서 접근해볼까요?

1. 오늘의 학습 키워드

큐
deque

2. 문제: 프로세스

단계: Lv. 2
출처: https://school.programmers.co.kr/learn/courses/30/lessons/42587

문제 설명

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

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번째로 실행됩니다.

3. 나의 풀이

접근 방법

큐, 스택 관련 문제를 접근할 때, 맨 처음 해야할 것은 deque 모듈을 불러오는 것입니다.

왜 deque를 통해 구현하면 좋을까요?

스택(stack)이나 큐(queue) 문제를 풀 때 list 대신 deque 모듈을 사용하는 이유는 deque가 양쪽 끝에서의 삽입과 삭제 연산이 더 효율적이기 때문입니다. 구체적으로 설명하자면:

시간 복잡도:

list에서의 append() 연산은 평균적으로 O(1)이지만, insert(0, item) 또는 pop(0) 연산은 O(n)의 시간 복잡도를 가집니다. 이는 리스트의 모든 요소를 이동시켜야 하기 때문입니다.

반면 deque는 양쪽 끝에서의 삽입(append, appendleft)과 삭제(pop, popleft) 연산 모두 O(1)의 시간 복잡도를 가집니다. 따라서, 큐나 덱(deque)와 같은 자료구조의 특성상 앞과 뒤에서의 연산이 빈번할 때 deque를 사용하는 것이 성능 면에서 훨씬 유리합니다.

큐(queue) 구현:

큐는 FIFO(First In, First Out) 구조로, 데이터가 들어온 순서대로 처리되어야 합니다. list를 이용할 경우 큐의 기능을 구현하려면 pop(0) 연산을 많이 사용해야 하는데, 이 경우 O(n)의 시간 복잡도를 가집니다.

deque는 앞에서 효율적으로 요소를 삭제할 수 있어 큐의 기능을 O(1)의 시간 복잡도로 구현할 수 있습니다.

스택(stack) 구현:

스택은 LIFO(Last In, First Out) 구조로, 가장 마지막에 들어온 데이터가 가장 먼저 처리됩니다. list의 경우 append()와 pop()을 사용하면 쉽게 스택을 구현할 수 있지만, 이 경우에도 deque는 비슷한 방식으로 O(1) 시간 복잡도로 동작합니다.

종합적으로, deque는 스택이나 큐를 구현할 때 더 효율적이고 성능 면에서 장점이 많기 때문에, list보다 선호되는 경우가 많습니다. 특히, 대량의 데이터 처리나 실시간 성능이 중요한 경우 deque를 사용하는 것이 좋습니다.

다시 문제로 돌아오겠습니다.

문제를 살펴보면 프로세스의 우선순위가 담겨있는 priorities 리스트, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location 정수가 인자로 주어졌을 때, location 에 해당하는 프로세스가 몇번째로 실행되는지를 리턴하는 문제입니다.

즉, location 은 process의 위치를 의미하고, 그 위치에 해당하는 process가 몇번째로 실행되는지를 파악하는 문제인 것입니다.

이제 한 줄씩, 코드 구현의 의미와 목적에 맞게 내용 설명을 진행해볼까요?

코드 개요

이 코드는 운영체제가 프로세스를 어떤 순서로 실행할지를 결정하는 시뮬레이션을 합니다. 주어진 프로세스들의 우선순위에 따라 특정 프로세스가 몇 번째로 실행되는지를 계산하는 문제입니다.

코드 설명

큐 생성 (queue = deque((i, p) for i, p in enumerate(priorities))):
- priorities 리스트의 각 요소와 그 인덱스를 쌍으로 묶어 deque(덱)로 변환합니다.
- 여기서 i는 프로세스의 인덱스이고 , p는 그 프로세스의 우선순위입니다.
- i 는 추후의 process의 위치인 location 파악을 위해 필요한 값입니다.
- 예를 들어, priorities = [2, 1, 3, 2]라면, queue는 deque([(0, 2), (1, 1), (2, 3), (3, 2)])가 됩니다.
반복문 (while queue:):
- 큐에 대기 중인 프로세스가 있을 때까지 반복합니다.
프로세스 꺼내기 (process = queue.popleft()):
- 큐에서 첫 번째 프로세스를 꺼냅니다. process는 (인덱스, 우선순위) 형태의 튜플입니다.
- 예를 들어, 처음에는 process = (0, 2)가 됩니다.
우선순위 비교 (if any(process[1] < q[1] for q in queue):):
- 현재 꺼낸 프로세스보다 높은 우선순위의 프로세스가 큐에 남아있는지 확인합니다.
- any() 함수는 queue에 있는 모든 프로세스의 우선순위를 검사하여, 만약 더 높은 우선순위의 프로세스가 있으면 True를 반환합니다.
- 예를 들어, 현재 process = (0, 2)이고, queue = deque([(1, 1), (2, 3), (3, 2)])라면, 우선순위 3이 있는 process (2, 3)이 있기 때문에 조건문이 참이 됩니다.
우선순위가 낮은 경우 다시 큐에 추가 (queue.append(process)):
- 만약 더 높은 우선순위의 프로세스가 큐에 있다면, 현재 프로세스를 다시 큐의 끝에 넣습니다.
- 그렇지 않은 경우 (else), 현재 프로세스를 실행(answer.append(process))합니다.
실행된 프로세스 기록 (answer.append(process)):
- 실행된 프로세스를 answer 리스트에 추가합니다.
- answer 리스트는 실행된 프로세스들의 순서대로 프로세스를 기록합니다.
결과 반환 (return answer.index(i) + 1):
- 최종적으로 answer 리스트에서 특정 위치에 해당하는 프로세스가 몇 번째로 실행되었는지 찾아서 반환합니다.
- location에 해당하는 인덱스를 가진 프로세스가 answer 리스트에서 몇 번째 위치에 있는지를 반환합니다.
- answer.index(i)는 0부터 시작하므로, 1을 더하여 몇 번째로 실행되었는지를 반환합니다.

동작 과정 예시

예를 들어 priorities = [2, 1, 3, 2]이고 location = 2일 때:

첫 번째로 (0, 2)를 꺼내고, (2, 3)이라는 더 높은 우선순위의 프로세스가 있으므로 (0, 2)를 다시 큐에 넣습니다.
두 번째로 (1, 1)을 꺼내고, (2, 3)과 (3, 2)가 더 높은 우선순위이므로 다시 큐에 넣습니다.
세 번째로 (2, 3)을 꺼내면, 더 높은 우선순위의 프로세스가 없으므로 이 프로세스를 실행합니다.
네 번째로 (3, 2)를 꺼내고 실행합니다.
마지막으로 (0, 2)를 꺼내고 실행합니다.
따라서 (2, 3)은 첫 번째로 실행됩니다.

이 코드에서 answer.index((2, 3)) + 1을 반환하게 되며, 이는 1을 반환합니다.

전체 코드는 아래와 같습니다:

from collections import deque

def solution(priorities, location):
    
    queue = deque((i,p) for i,p in enumerate(priorities))  # i는 index, p는 우선순위
    answer = []
    
    while queue: 
        
        process = queue.popleft() # 1. 큐에서 대기중인 프로세스를 하나 꺼냄
        # print(process)
        if any(process[1] < q[1] for q in queue): # 2. 큐에서 대기중인 프로세스중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 process[1]를 다시 큐에 넣음.
            queue.append(process)
        else: # 3. 없다면 방금 꺼낸 프로세스를 실행
            answer.append(process)
            
    for i in answer:
        if i[0] == location:
            return answer.index(i) + 1

4. 결론

이번 문제는 실질적으로 큐 자료구조를 사용하는 프로세스 스케쥴링의 내용을 코딩 테스트 문제화 시킨 문제였습니다. 진짜 조만간에 스택, 큐 자료 구조 관련 문제들을 쫙 풀어볼 예정이였는데 이렇게 99클럽에서 제공하는 문제가 우연치 않게 큐 문제가 나왔네요.

이 문제를 며칠 뒤에 다시 풀어보고 나머지 스택, 큐 자료구조 관련 문제들을 다 모아 한 번 정리하는 내용의 포스팅을 진행하도록 하겠습니다.

아 참! 그리고 스택, 큐 자료구조는 제 벨로그에 정리한 내용이 있으니, 보고 참고하시면 좋을것 같습니다.

읽어주셔서 감사합니다! 댓글, 좋아요는 언제나 환영입니다!!

말하는 감자

할 수 있다

이전 포스트

99클럽 코테 스터디 27일차 TIL (공원 산책) - 프로그래머스

다음 포스트