.png)
🔎 문제
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
- 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
- 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
- 그렇지 않으면 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로 표현합니다.
💻 입출력 예
📄🤔 코드 및 풀이과정
🔹 1번
public static int solution(int[] priorities, int location) {
Queue<Integer> q = new LinkedList<>();
for (int i : priorities) {
q.add(i);
}
Integer[] arr = new Integer[priorities.length];
for (int i = 0; i < priorities.length; i++) {
arr[i] = priorities[i];
}
int count = 0;
Arrays.sort(arr, Collections.reverseOrder());
out:
for (int i = 0; i < arr.length; i++) {
while(true) {
if(arr[i] == q.peek()) {
q.remove();
count++;
location--;
if(location==-1) break out;
break;
}else {
q.add(q.poll());
location--;
if(location==-1) location = q.size()-1;
}
}
}
return count;
}🔸 1번 풀이
처음 코드는
FIFO의 특성을 가진 Queue에 기존 프린터 대기목록을 넣고,
Arrays.sort와 Collections.reverseOrder()를 통해
기존 프린터 대기목록이 내림차순으로 정렬된 arr 배열을 만들었다.
내림차순 배열을 만든 이유는
우선순위가 높은 것을 먼저 출력해야 하기에
대기목록의 프린터 우선순위를 높은 것부터 정렬해두고
큐에 가장 먼저 들어온 값과 비교해서 배열의 첫 번째 값과 일치할경우
프린트해서 큐에서 빼버리고,
그렇지 않다면 큐에서 뺀 뒤 큐의 마지막에 집어 넣기 위함이다.
for 반복문은 내림차순으로 정렬된 배열을 순차적으로 돌면서
큐에서 높은 우선순위를 가진 작업을 만날때까지 while문이 돌고
만난다면 큐에서 제거 후 count를 증가(출력한 문서 수 기록용)시킨다.
location을 감소시키는 이유는
이 문제가 location번째 문서가
몇번째로 출력되는지를 반환해야 하는 문제기 때문이다.
앞에 문서들이 출력되거나 뒤로 빠질때마다 location번째 문서의 location값(위치 인덱스값)은 1씩 감소된다.
만약 출력되길 원하는 문서가 프린트 될 경우
if(location==-1) break out 을 통해 명명된 for 반복문을 빠져나가고 현재 출력 수를 반환한다.
만약 location이 -1인데 우선순위가 남아있는 문서들보다 낮을 경우
출력을 할 수 없기 때문에
while문 내부의 else에 있는
if(location==-1) location = q.size()-1 을 통해
location값은 큐의 마지막 위치의 인덱스를 가지며
큐의 마지막에 추가되게 된다.
Integer타입의 배열을 만든 이유는
Arrays.sort()를 사용하며 비교측정기를 사용할 시
int 배열을 정렬할 수 없어 Integer 배열에 옮겨 담은 뒤에
내림차순으로 정렬한 것이다.
이런 방식으로 문제를 풀어 통과하였는데
정렬을 위해 Integer 배열을 만들면서 낭비되는 처리와
반복문에 명명을 하고 break로 빠져나가는 방식이
그리 효율적이고 깔끔해보이지 않았기 때문에
추가적으로 수정을 해 보았다.
🔹 2번
public static int solution(int[] priorities, int location) {
Queue<Integer> q = new LinkedList<>();
for (int i : priorities) {
q.add(i);
}
int count = 0;
Arrays.sort(priorities);
for (int i = priorities.length-1; i >= 0 ; i--) {
while(true) {
location--;
if(priorities[i] == q.peek()) {
q.remove();
count++;
if(location==-1) return count;
break;
}else {
q.add(q.poll());
if(location==-1) location = q.size()-1;
}
}
}
return count;
}🔸 2번 풀이
1번 코드에서 내림차순을 하며 비교측정기를 사용하기 위해
Integer 배열을 만들었었다.
그런데 생각해보니 Arrays.sort로 오름차순 정렬을 하고
배열의 뒤에서부터 반복문으로 값을 가져오면
구지여 내림차순을 하지 않고도 내림차순처럼 높은 순서대로
우선순위를 가져올 수 있다는 생각이 들었다.
그래서 Integer 배열을 없애고, 우선순위 배열을 오름차순 정렬하고
for문을 뒤에서부터 돌도록 변경했다.
또한 if(location==-1) break out;
으로 외부 반복문을 빠져나간 뒤 return하는 방식에서
if(location==-1) return count;
으로 그냥 바로 count를 리턴하고 메서드를 종료하는 방식으로 변경했다.
어차피 외부 반복문을 종료하고 나서 return만 할 것이라면
그냥 외부 반복문을 종료 하는 시점에
return해버리는 쪽이 더 나으리라 생각했기 때문이다.
location--도 if, else문에 각각 하나씩 넣어뒀었는데
어차피 while문을 돌때마다 실행되는 것이기 때문에
중복이라 생각하여 조건문 위로 빼 한줄로 줄였다.
대규모 데이터를 처리하는 문제는 아니라
제출 시 처리속도는 크게 감소하지 않았지만
첫 번째 코드보다 훨씬 간결해졌다.
😳❕ 소감 & 느낀점
큐는 이번에 처음 사용해보았다.
이론 공부를 하면서 예제로 사용은 해봤지만
이렇게 실제로 문제에 접목해서 문제 해결을 위해 사용해 본 적은 처음이다.
배우기만 하고 제대로 써본적이 없었기에
이번 문제를 풀며 조금 애를 먹은 것 같다.
그래도 직접 써보며 어떤 메서드가 있는지 되돌아보고
각 메서드의 기능이나 반환값 등을 확인, 사용하는 과정에서
조금이나마 내 것으로 만들 수 있었던 것 같다.
List, Set, Map, Queue, Stack...
세부적으로 들어가면 이 외에도 정말 많은 컬렉션들이 존재하는데
어떠한 문제를 마주했을 때 이들을 적재적소에 사용하며
효율적으로 문제를 해결할 수 있는 개발자가 되기 위해
좀더 자주, 많은 컬렉션들을 사용해봐야겠다 :)
