[모각코 / 240119] 알고리즘 문제 풀이 (프로그래머스 - 스택/큐)

 

 

안녕하세요. 모각코 3일차입니다.

 

 

 

오늘은 프로그래머스를 이용하여 스택 / 큐 유형의 문제를 풀어보았습니다. 

 

 

문제 이름은 프로세스로 우선순위 큐 문제였습니다. 

https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

 

 

 

입출력 양식입니다. 

프로그래머스는 코드트리나 백준과 달리 함수의 형태로 제출합니다. 

priorities | location | return
 [2,1,3,2]      2         1
 [1,1,9,1,1,1]  0         5

 

 

입출력 양식을 그림으로 그려보았습니다. 

가장 왼쪽의 값을 꺼내고 그 값보다 우선 순위 값 중 더 큰 값이 있으면 값을 맨 뒤로 보냅니다. 

 

 

풀이 방법입니다. 아주 정석적인 풀이는 아닌 것 같지만 설명을 진행해보겠습니다. 

 

저는 deque를 사용해서 구현을 했고 deque를 두 개 사용했습니다. 하나는 값이 들어가는 용도, 하나는 인덱스 값이 들어가는 용도로 사용합니다.

꺼내는 값이 priorities에서 가장 큰 값보다 작으면 deque 오른쪽에 값을 추가합니다. 꺼내는 값이 작거나 같으면 결과 리스트에 인덱스 번호를 추가합니다. 이는 이미 꺼내진 값의 인덱스입니다. 

그리고 priorities의 값도 remove 함수를 통해서 지워줍니다. 

from collections import deque

def solution(priorities, location):
    q = deque()  # 값을 빼내는 용도의 큐 생성
    index = deque()  # 인덱스가 들어갈 큐 생성
    result = []
    for i in range(len(priorities)):
        q.append(priorities[i])  
        index.append(i)
    while q:
        first = q.popleft()
        i = index.popleft()
        if max(priorities) > first:  # 빼낸 값보다 우선순위가 더 크면
            q.append(first)
            index.append(i)
        else:  # 왼쪽의 값을 꺼내도 되면
            result.append(i)
            priorities.remove(first)
    for i in range(len(result)):
        if location == result[i]:
            return i+1

 

 

생각해보니 deque 하나만 사용해도 위의 방식으로 풀 수 있을 것 같아서 리펙토링을 해봤습니다. 

from collections import deque

def solution(priorities, location):
    q = deque()
    result = []
    for i in range(len(priorities)):
        q.append((priorities[i], i))  
    while q:
        first, i = q.popleft()
        if max(priorities) > first: 
            q.append((first, i))
        else:
            result.append(i)
            priorities.remove(first)
    for i in range(len(result)):
        if location == result[i]:
            return i+1