[프로그래머스](파이썬)-이중 우선순위큐-Level2.5-힙,큐 문제

안녕하세요. 진또배기입니다. 오늘은 프로그래머스의 이중 우선순위큐 문제를 풀어보도록 하겠습니다.

음 제 생각에는 이런 문제는 복잡한 알고리즘은 쓰이지 않지만 다양한 스킬들과 2가지의 자료구조가 쓰이기때문에 2.5레벨의 문제라고 생각합니다. 이 정도 난이도의 문제는 현재 한국 대기업에서 가장 어려운 코딩테스트 문제에요. 물론 Level4, Level5의 문제도 있지만 거기까지는 나오지 않는 것 같습니다. (네이버, 카카오, 구글, AWS 등 자체 IT서비스 기업제외-여긴 더 어려운 문제나옴..ㅋㅋ)

그러면 시작하겠습니다!

1. 문제 소개

문제 설명

급한 일을 먼저 처리해주는 서버가 있습니다. 이 서버에 3초에 한 번씩 요청이 들어온다고 할 때, 서버가 각 요청을 처리하는 순서를 알아보려 합니다. 요청은 [요청의 순위(높을수록 급한 요청), 요청을 처리하는데 걸리는 시간] 형식으로 주어지며, 서버가 요청을 처리하는 방식은 다음과 같습니다.

• 서버는 처리 중인 요청을 모두 끝낸 후 다른 요청을 처리합니다.
• 작업 중인 요청이 끝난 시점에 새 요청이 들어오는 경우, 대기 중인 요청과 새 요청 중 더 급한 요청을 먼저 처리합니다.

예를 들어 3초마다 다음과 같은 요청이 들어왔습니다: [1, 7], [4, 1], [5, 2], [3, 1], [7, 2]
이 경우 서버는 다음과 같이 행동합니다.

제한 사항

• reqs의 길이는 1 이상 100,000 이하입니다.
• reqs의 원소는 [요청의 순위(높을수록 급한 요청), 요청을 처리하는데 걸리는 시간] 형식입니다.
  • 요청의 순위는 1 이상 100,000 이하인 자연수입니다.
  • 요청을 처리하는데 걸리는 시간은 1 이상 10 이하인 자연수입니다.
  • 순위가 같은 요청이 있는 경우는 주어지지 않습니다.

#예제 2

---

2. 슈도 코드

문제가 많이 복잡하죠?

우선, 우리가 할일을 순서대로 정리해봅시다.

-3초마다 서버에 요청을 하나씩 날려야 하겠습니다.

-서버에 작업이 끝나면,
   들어온 요청 중 가장 우선순위가 높은 요청을 찾습니다.
        그 요청을 작업이 끝난 해당 서버에 넣어줍니다.

----->요청이 들어오고 나가는 와중에 제일 높은 값을 찾아주어야 합니다.

따라서 진짜 슈도코드는 

1. 필요 변수 설정
-3초에 한번 요청이 들어오게 한다.
-서버에 들어온 요청이 어딘가 모여 있어야한다.
-서버가 처리중인 작업을 끝내면 새 요청을 처리하게 만들어야 한다.

-현재 시각을 트래킹하는 변수 필요, 요청을 저장하는 공간(힙)필요, 작업이 끝나는 시각을 위한 변수 필요

2. 반복문을 돌며 일 처리
-3초마다 서버에 요청을 하나씩 넣는다
-서버는 처리중인 요청이 끈났으면 힙에서 우선순위가 가장 높은 요청을 꺼낸다.
     ->이때 작업이 끝나는 시각을 업데이트한다.
-현재 시각을 1 증가시킨다.

---

3. 문제 풀이

코드에 대한 설명은 주석으로 처리하였습니다.

---

4. 알아야할 스킬 셋

 저는 인덱스의 위치를 계속 저장해주기 위해 enumerate라는 함수를 사용했습니다.

reqs = deque([req + [i] for i, req in enumerate(reqs, 1)])

enumerate 는 ‘열거하다’라는 단어입니다. 파이썬에서는 List , Tuple , String 등 여러가지 자료형을 입력받으면 인덱스 값을 포함하는 enumerate 객체를 돌려줍니다. 보통 enumerate 함수는 for문과 함께 자주 사용합니다.
보통

for 인덱스, 값 enumerate(배열, 시작 인덱스)

로 코딩합니다.
다양한 예시로 enumerate()에 익숙해져보겠습니다.

예제1)
itemx = ["First", "Second", "Third"] 
for i, val in enumerate(itemx, 10): 
    print("{} 번째 값은 {}입니다".format(i, val))
>>> 10 번쨰 값은 First입니다
>>> 11 번쨰 값은 Second입니다
>>> 12 번쨰 값은 Third입니다

예제2
a = ['hong','gil','dong']
b= []
for i,name in enumerate(a):
    b.append((i,name))
print(b)
>>> [(0, 'hong'), (1, 'gil'), (2, 'dong')]

예제3)
items = [[30,100],[500,30],[100,400]]
items0 = [(*item, idx) for idx, item in enumerate(items,1)]
items0
>>> [(30, 100, 1), (500, 30, 2), (100, 400, 3)]
# *는 unpack 작업을 수행한다.
items1 = [(item, idx) for idx, item in enumerate(items,1)]
items1
>>> [([30, 100], 1), ([500, 30], 2), ([100, 400], 3)]

다양한 방법으로 인덱스위치를 저장할 수 있습니다.

 

단, enumerate(배열)처럼 인덱스 위치를 지정하지 않으면 디폴트 값으로 인덱스위치는 0부터 시작하게 됩니다.

오늘은 프로그래머스의 이중 우선순위큐에 대해 알아보았습니다.
항상 감사합니다.

-진또배기 올림