Algorithm
[프로그래머스] 프로세스
쑤야.
2023. 12. 20. 14:26
https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=python3
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
접근
- enqueue와 dequeue가 반복되는데, 우선순위 값은 중복될 수 있으므로 타겟 구분을 위해 인덱스 값 저장이 필요
로직
- (인덱스, 우선순위)을 데이터로 저장
- priorities를 오름차순 정렬을 통해 마지막 원소를 기준으로 현재 가장 높은 우선순위가 무엇인지, 제거해야 하는 우선순위가 무엇인지 판별한다.
- 내림차순 정렬로 첫 번째 원소를 기준으로 할 경우, 삭제할 때 시간복잡도가 O(N)이 되므로 오름차순을 사용한다.
- 타켓 원소를 제거할 때까지 반복문을 돌리며, 가장 첫 번째 원소를 일단 pop 한다.
- pop한 원소에 대해 아래의 로직을 수행한다.
- 현재 가장 높은 우선순위이며, 제거해야 하는 타켓인 경우 반복문을 종료한다.
- 현재 가장 높은 우선순위이지만, 제거해야 하는 타켓이 아닌 경우 priorities 마지막 원소만 제거한다.
- 현재 가장 높은 우선순위가 아닐 경우, 다시 데이터 큐 마지막 위치에 넣어준다.
코드
def solution(priorities, location):
data = [(i,p) for (i,p) in enumerate(priorities)]
priorities.sort()
result = 0
while len(data) != 0:
pop = data.pop(0)
if priorities[-1] == pop[1]:
result += 1
if pop[0] == location:
break
else:
priorities.pop()
continue
else:
data.append(pop)
return result