[알고리즘 문제풀이] 프로그래머스 - 프린터

yourjin·2022년 2월 27일

level2 알고리즘 큐(Queue)

알고리즘 문제풀이

목록 보기

17/28

TIL (2022.02.22)

➕ 오늘 푼 문제

프로그래머스 - 프린터

➕ 아이디어

큐에 프린트 물의 인덱스와 우선순위를 함께 저장한다.
큐에 원소가 2개 이상인 동안,
- 큐에서 원소를 뽑는다.
- 남은 큐에서 우선순위가 최대인 값을 뽑는다.
- 최대 우선순위가 현재 원소의 우선순위보다 크다면, 다시 큐에 넣는다.
- 아니라면 인쇄하고(answer += 1 ), 현재 원소가 location과 같은 지 확인한다.
  - 같다면 인쇄 횟수를 반환한다.
큐에 원소가 남았다면, 그 원소가 location 일 것이므로 인쇄 횟수 + 1을 해준다.

➕ Java 코드

import java.util.*;

class Paper implements Comparable<Paper>{
    private int location;
    private int priority;

    Paper(int location, int priority){
        this.setLocation(location);
        this.setPriority(priority);
    }

    public Integer getPriority() {
        return priority;
    }

    public void setPriority(int priority) {
        this.priority = priority;
    }

    public int getLocation() {
        return location;
    }

    public void setLocation(int location) {
        this.location = location;
    }

    @Override
    public String toString() {
        return "Paper [location=" + location + ", priority=" + priority + "]";
    }

    @Override
    public int compareTo(Paper o) {
        // TODO Auto-generated method stub
        return getPriority().compareTo(o.getPriority());
    }

}

class Solution {
    public int solution(int[] priorities, int location) {
               int answer = 0;
        Queue<Paper> q = new LinkedList<Paper>();

        for(int i=0; i<priorities.length; i++){
            q.offer(new Paper(i, priorities[i]));
        }
        

        while(q.size() > 1){
            Paper p = q.poll();
            Paper maxPriorityPaper = Collections.max(q);
            if (p.getPriority() < maxPriorityPaper.getPriority()){
                q.offer(p);
            }else{
                answer += 1;
                if(location ==  p.getLocation()){
                    return answer;
                }
            }
        }

        if(!q.isEmpty()){
            answer += 1;
        }

        return answer;
    }
}

➕ Python 코드

from collections import deque

def solution(priorities, location):
    answer = 0
    q = deque([])

    for i in range(len(priorities)):
        q.append((i, priorities[i]))

    while len(q) > 1:
        n, p = q.popleft()
        max_priority = max(q, key=lambda x:x[1])[1]
        if max_priority > p:
            q.append((n, p))
        else:
            answer += 1
            if location == n:
                return answer
    
    if q:
        answer += 1

    return answer

➕ 궁금한 내용 및 소감

아이디어 그대로 구현하면 되는 문제였지만, 역시나 구현이 약간 까다로운 문제였다. 여러 방식으로 구현할 수 있는데, 이번에는 max 함수를 통해 큐에서 최대값을 뽑아낼 수 있게 하였다. 이게 아니라면 큐를 순회하면서 최대값을 뽑을 수도 있다. (시간복잡도를 비교해보지 않았지만, 아마 내장 함수를 사용하는 것이 효율이 더 좋았을 것 같다.)
이번에는 자바에서 정렬 뿐만 아니라 max/min을 구할 때도 Comparable/Comparator 가 사용될 수 있음을 알았다. 여러모로 활용도가 높은 인터페이스라서 빨리 사용에 익숙해졌으면 좋겠다!