(알고리즘 스터디) 3주차 월 _ 스택&큐📦 _ (Programmers) 프린터

🌟 프로그래머스 / 스택&큐 / Level2 / 프린터

📃 문제

프로그래머스

🚫 제한 사항

• 현재 대기목록에는 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

🤔 풀이 방법

1️⃣ 자료구조 사용

➡️ 앞에서 빼고, 만약 우선 순위가 더 높은 문서가 있다면 뒤로 넘어가는 원리이므로 Queue 가 적합

2️⃣ 같은 우선 순위 일 때 location 값을 구분하는 방법

➡️ 가장 오랫동안 고민한 부분 중 하나이다. 큐에 넣고 돌리다보면 인덱스를 하나하나 신경쓸 수 있는 것이 아닌데 어떻게 같은 우선 순위를 가진 요청들 사이에서 인덱스를 확인하는지가 문제였다.

Map 이나 배열 활용 등의 방법을 생각해보았지만 비효율적인 부분들도 많았고, 원하는 형태도 아니였다.

그러던 중 과거 비슷한 문제에서 클래스를 따로 생성하여 담았던 기억이 있어서 아래와 같은 구조를 생각하면서 job 클래스를 생성한 뒤 큐에 넣어 주었다.

 

① job 클래스

class job {
    int index; // 배열에서의 index (= location)
    int priority; // 배열에서의 원소값 (= 우선순위)
    
    public job (int index, int priority) {
        this.index = index;
        this.priority = priority;
    }
}

 

② Queue 를 생성하여 넣어주는 과정

class Solution {
    // 전역변수로 큐 생성
    public static Queue<job> q = new LinkedList<job>();
    
    public int solution(int[] priorities, int location) {
        
        // 반복문을 통해 차례대로 큐에 넣어줌
        for (int i=0; i<priorities.length; i++) {
            q.add(new job(i, priorities[i])); // job 객체 생성 후 추가
        }
    }

 

③ 최종 구조 

➡️ 주어진 배열이 [2, 1, 3, 2] 라고 할 때,

설계 구조

3️⃣ 탐색 과정

① 일단 주어진 배열을 정렬하여 우선순위를 오름차순 정렬 하였다.

// 기존 배열 : int[] arr -> [2, 1, 3, 2]
Arrays.sort(arr);
// 정렬 후 : [1, 2, 2, 3]

➡️ 뒤에서부터 하나씩 앞으로 가면 출력해야할 우선 순위 번호를 알 수 있다.

 

② printer() 함수를 구현하여 출력되는 job 객체를 반환하도록 하였다.

/*
리턴값 : 출력되는 job 객체
파라미터 : 출력되어야하는 우선순위 값
*/
public static job printer(int max) {
        job j;
        while (true) { // 출력되어야할 job 을 찾을 때 까지 반복
            j = q.remove(); // 큐에서 첫번째 job 을 제거
            if (j.priority == max) { // 해당 job 의 우선순위가 넘겨받은 인자값과 동일한지 확인
                return j; // 동일하면 해당 job 을 리턴
            }
            q.add(j); // 일치하지 않는다면 맨 뒤로 보내고 다시 반복
        }
}

 

③ printer() 함수로 부터 반환 된 job 의 index 값이 location 과 같다면 answer 값을 리턴

while (j.index != location) { 
// 우선순위가 같은 job 이라도 찾던 location 값을 가진 job 이 아니라면 계속 진행
    answer++;
    prior = priorities[priorities.length-answer];
    j = printer(prior);
}

💻 풀이 코드

import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

// job class 생성
class job {
    int index; // 변수① : priorities 배열에서의 index 값
    int priority; // 변수② : priorities 배열에서의 원소 값
    
    public job (int index, int priority) { // 생성자
        this.index = index;
        this.priority = priority;
    }
}

class Solution {
    // 전역변수로 Queue 생성
    public static Queue<job> q = new LinkedList<job>();
    
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        // 기존 priorities 배열의 값들을 job 객체로 생성하여 큐에 넣어줌
        for (int i=0; i<priorities.length; i++) {
            q.add(new job(i, priorities[i]));
        }
        
        job j = new job(-1, -1); // 반복문을 위한 job 객체 생성
        
        int prior = 0; // 변수 : 우선 순위 번호
        Arrays.sort(priorities); // 우선 순위 확인을 위한 배열 정렬
        
        while (j.index != location) { 
        // 작업해야할 job 의 index 가 location 과 같아질 때까지 반복
        // 만약 같은 우선순위의 작업물이 출력되었더라도 index 가 맞지 않으면 멈추지 않음
            answer++;
            // 배열의 마지막 (제일 큰값) -> 배열의 첫번째 (제일 작은값) 순서로 탐색
            prior = priorities[priorities.length-answer];
            // 출력할 job 입력받음
            j = printer(prior);
        }
        
        return answer;
    }
    /*
    파라미터
    ① max : 출력해야할 우선순위 값
    리턴값
    ➡️ 출력되야할 job
    */
    public static job printer(int max) {
        job j; // 반복물을 위한 job 객체 생성
        while (true) { // job 을 찾을 때까지 반복됨
            j = q.remove(); // Queue 에서 head 에 있는 첫번째 job 제거
            if (j.priority == max) { // 해당 job 의 우선순위값 확인
                return j; // 동일하면 해당 job 리턴
            }
            q.add(j); // 아닐 경우 Queue 의 맨 뒤에 넣어주고 반복문 계속 진행
        }
    }
}

[level 2] Title: 프린터, Time: 1.24 ms, Memory: 73.7 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@426b0d8