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

cgw0519·2021년 5월 4일
0

알고리즘 문제풀이

목록 보기
16/19

오늘 푼 문제는 프로그래머스 고득점 Kit 스택/큐 분류에 있는 Level2 문제이다 !
https://programmers.co.kr/learn/courses/30/lessons/42587
( 스택/큐도 다 뿌셨다 ~~~! ✅ )

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

  1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
  2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
  3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

  • 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
  • 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
  • location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

입출력 예

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

풀이 방법

먼저 프린터에서 각 작업이 순서가 바뀌더라도 처음의 위치를 기억하고 있어야지만, 문제에서 요구한 위치의 작업이 몇 번째로 수행되었는지 반환할 수 있다. Job이라는 클래스를 만들어 중요도와 위치를 저장해주고 Job 객체를 저장하는 큐를 생성하여 작업들을 순차적으로 넣어주었다.

작업들은 큐에 순서대로 저장을 하였으니 매개변수로 받은 priority는 정렬하여 현재 가장 높은 중요도가 무엇인지 판단하는 용도로 사용하였다.

큐의 맨 앞에 있는 작업이 가장 높은 중요도를 가지는지 확인한다.

  1. 맞다면, 문제에서 요구한 위치의 작업인지 확인하고 맞으면 현재까지 프린트된 작업 수를 저장하고 있는 변수를 반환한 후 종료하고, 아니라면 현재 작업을 수행한다는 의미로 작업을 큐에서 제거한다.
  2. 아니라면, 즉 더 높은 우선순위의 작업이 뒤에 있다면 현재 작업은 빼낸 후 큐의 맨 뒤에 다시 넣어준다.

여기서 프린트된 작업 수를 저장하는 데에 사용된 변수는 초기 값을 1로 설정하여 실제 프린트된 작업보다 1씩 크게 해주었다. 그 이유는 priority 배열이 오름차순으로 정렬되어서 맨 끝에부터 탐색을 해야하는데 length-1을 해주는 것을 피하기 위해서이다 ! 또한 결과 값을 반환할 때 location이 일치하는 것을 확인한 후 현재 작업에 대한 1을 따로 더하지 않고 반환할 수 있기 때문이다.

아주아주 간단한 문제여서 고민없이 바로 문제를 풀 수 있었고, 풀이와 코드를 보는 분들도 쉽게 이해할 수 있을 것이다 ~

코드

import java.util.*;
class Solution {
    public static class Job{
        private int priority;
        private int location;
        Job(int priority, int location){
            this.priority = priority;
            this.location = location;
        }
    }
    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<Job> printerQueue = new LinkedList<>();
        for(int i=0; i<priorities.length; i++) printerQueue.add(new Job(priorities[i], i));
        Arrays.sort(priorities);
        int printed = 1;
        while(!printerQueue.isEmpty()){
            if(printerQueue.peek().priority == priorities[priorities.length-printed]){
                if(printerQueue.peek().location == location) return printed;
                printerQueue.poll();
                printed++;
            }
            else{
                Job job = printerQueue.poll();
                printerQueue.add(job);
            }
        }
        return answer;
    }
}
profile
Android Developer

관심 있을 만한 포스트

0개의 댓글