[프로그래머스 Lv.2] 프린터

코딩테스트 연습 - 프린터

문제 설명

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

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로 표현합니다.

풀이

To-Do 리스트

결과

💥 코딩테스트 문제풀이 제한시간 50분, 시간 초과.

알게 된 점

💯 클래스를 만들어서 접근하는 방법

import java.util.*;
class Solution {
  static class doc{
    int prior;
    int location;
    
    public doc(int prior, int location) {
      this.prior = prior;
      this.location = location;
    }
  }
    public int solution(int[] priorities, int location) {
int answer = 0;
    int cnt = 0;
    
    Stack<doc> stk = new Stack<>();
    List<Integer> list = new ArrayList<>();
    
    for (int i = 0; i<priorities.length; i++) {
      int p = priorities[i];
      
      doc d = new doc(p, i);
      stk.add(d);
      
      list.add(p);
    }
    // 역순으로 정렬
    Collections.sort(list, (o1, o2) -> o2.compareTo(o1));
    
    int max = list.get(0);
    
    while(!stk.empty()) {
      doc d = stk.get(0);
      stk.remove(0);
      
      if(d.prior == max) {
        list.remove(0);
        if(!stk.isEmpty()) max = list.get(0);
        cnt++;
        if(d.location == location) {
          answer = cnt;
        }
      }else {
        stk.add(d);
      }
    }
   
    return answer;
    }
}

💯 Queue 하나로 접근하는 방법

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        int l = location;

        Queue<Integer> que = new LinkedList<Integer>();
        for(int i : priorities){
            que.add(i);
        }

        Arrays.sort(priorities); //정렬을 통해서 max값을 구하려 노력.
        int size = priorities.length-1; // max값의 idx위치



        while(!que.isEmpty()){ //큐 가 비어있지 않은 경우에 
            //큐 맨 앞에 있는 값 반환 후 삭제, 큐가 비어있을 경우 null 반환
            Integer i = que.poll(); 
  			// max위치의 값과 que 맨 앞에 있는 값 비교
            if(i == priorities[size - answer]){ 
                answer++; // 제일 큰값 제거 완료했으므로, 1을 더함.  
                l--; // 요청하는 위치의 결과값을 찾기위해 진행.
                if(l <0) // 요청하는 위치의 결과값을 찾음.
                    break;
            }else{
                que.add(i); // 맨뒤로 값을 옮김.
                l--; // 요청하는 위치의 결과값을 찾기위해 진행.
                if(l<0) 
                    l=que.size()-1;
            }
        }

        return answer;
    }
}