[프로그래머스] 스택/큐 - 프린터 문제 풀이

오늘은 스택/큐 문제 중에서 "프린터" 문제를 풀어보겠습니다. 이번 문제는 스택/큐 알고리즘을 활용하는 문제로 보이는데, 과연 어떤 방법으로 문제를 풀게 될지 시작 전에 호기심을 갖고 시작하게 됩니다. 일전에도 공부했던 스택과 큐의 알고리즘이기에 이전 포스팅 참고하시고 문제 풀이 들어가보겠습니다.

 

 

 

 

2022.03.18 - [컴공생의 Specification/TypeScript] - [JavaScript] Stack과 Queue 만들기

[JavaScript] Stack과 Queue 만들기

 

 

 

 

프로그래머스 > 스택/큐 > 프린터 문제 풀이

 

 

 

 

▼ 문제 정보

• 문제명: 프린터
• 문제 난이도: Level 2
• 문제 푼 사람수: 31503명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

 

▼ 문제 설명

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

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. 먼저 맨 앞에 있는 문서를 꺼낸다.
  2. 대기 목록 중 우선순위가 높은(숫자가 큰) 문서가 있다면 꺼낸 문서는 맨 뒤로 이동한다.
  3. 대기 목록 중 우선순위가 더 높은 문서가 없다면 인쇄한다.
     이 때, 출력되는 문서가 내가 요청한 문서인지 확인하고, 맞다면 출력 순서를 반환한다.
•  Inputs
  • priorities: 문서의 중요도가 담긴 인쇄 대기 목록 리스트 (숫자 배열)
  • location: 내가 인쇄를 요청한 문서의 대기 목록 위치
• output: 내가 인쇄를 요청한 문서가 출력된 순서

 

 

 

 

▼ 제한사항

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

 

 

위 제한사항에서 주요 사항은 대기목록 최대 숫자가 100이라는 부분입니다. 이 것은 바로 효율성 테스트 케이스는 없는 문제라는 부분입니다. 그리고 아래는 제한사항을 정리한 내용입니다.

 

• 1 ≤ 대기목록 수 ≤ 100
• 1 ≤ 인쇄 작업 우선순위 ≤ 9
• location은 배열의 index

 

 

 

 

▼ 입출력 예

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

 

 

 

 

▼ 입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.

 

 

 

 

▼ 알고리즘 만들기

이번 문제는 문제 설명에서 알고리즘이 도출될 수 있는 문제입니다. 즉, 문제 설명에 나온 순서대로 알고리즘을 나열하면 바로 알고리즘이 만들어지는 것이라 생각합니다. 그럼 아래 문제 설명대로 만들어진 알고리즘 확인하러 가보시겠습니다.

 

 

1. 인쇄 목록 리스트를 순회하며 맨 앞의 인쇄 문서를 선택하여 꺼낸다. ★ Dequeue
2. 선택된 인쇄문서의 우선순위보다 현재 리스트의 인쇄 우선순위가 높은 문서가 있는지 확인한다.
   2-1. 현재 문서가 가장 우선순위가 높을 경우, 출력하며, 출력 순서를 카운트한다.
      2-1-1. 이 때, 출력하는 문서의 위치가 location과 같다면 3으로 이동한다.
      2-1-2. 같지 않다면, 1로 이동하여 계속 순회한다.
               (현재 문서의 위치 계산을 위해 우선순위가 가장 낮은 0인 문서를 맨 뒤에 넣는다.) ★ Queue
   2-2. 현재 리스트에 우선순위가 높은 문서가 있을 경우, 현재 문서를 맨 뒤에 넣는다. ★ Queue
3. 현재 문서가 몇번째 출력했는지 반환한다.

 

 

위 알고리즘은 FIFO 방식의 자료구조인 Queue를 이용하여 만들어보았습니다. 문제 설명에서 나온 1, 2, 3 순서가 결국 Queue 자료구조를 뜻했기에 그 방법 그대로 만들어보았습니다. 그럼 바로 코드 구현으로 넘어가보겠습니다.

 

 

 

 

▼ 코드 구현

function solution(priorities, location) {
    let answer = 0;
    let curIndex = 0;
    const N = priorities.length;
    
    // 1. 인쇄 목록 리스트를 순회하며
    while(priorities.length !== 0) {
    	// 맨 앞의 인쇄 문서를 선택하여 꺼낸다. ★ Dequeue
        const selectedPriority = priorities.shift();
        // 2. 선택된 인쇄문서의 우선순위보다 현재 리스트의 인쇄 우선순위가 높은 문서가 있는지 확인한다.
        if(selectedPriority !== 0 && priorities.find(priority => priority > selectedPriority) === undefined) {
            // 2-1. 현재 문서가 가장 우선순위가 높을 경우, 출력하며, 출력 순서를 카운트한다.
            answer++;
            // 2-1-1. 이 때, 출력하는 문서의 위치가 location과 같다면 3으로 이동한다.
            if(curIndex === location) {
                break;
            }
            // 2-1-2. 같지 않다면, 1로 이동하여 계속 순회한다.
            // (현재 문서의 위치 계산을 위해 우선순위가 가장 낮은 0인 문서를 맨 뒤에 넣는다.) ★ Queue
            priorities.push(0);
        } else {
            // 2-2. 현재 리스트에 우선순위가 높은 문서가 있을 경우, 현재 문서를 맨 뒤에 넣는다. ★ Queue
            priorities.push(selectedPriority);
        }
        curIndex = (curIndex + 1) % N;
    }
    // 3. 현재 문서가 몇번째 출력했는지 반환한다.
    return answer;
}

 

 

코드가 어떤가요? 알고리즘 그대로 구현했기에, 다소 복잡하고 효율이 부족할 수 있습니다. 이 부분은 마지막에서 언급하도록 하겠습니다.

 

 

 

 

▼ 채점 결과

 

 

이 문제의 의도대로 큐를 활용한 알고리즘을 통해 정확성 테스트 케이스 20개를 모두 통과하였습니다.

그럼 알고리즘을 더 효율적으로 만들 수 없을까에 대한 심화과정으로 넘어가보겠습니다.

 

 

 

 

▼ 심화 과정

여기까지 오셨다면 여러분은 스택/큐의 프린터 문제 풀이를 완료하신 겁니다. 하지만 진짜 개발자라면 큐를 활용한 위 알고리즘이 정말 효율적이고 최선의 답인지 의심을 품고 계시는 분들이 있을 거라 생각합니다. 그래서 이 심화 과정을 남기려고 합니다.

 

 

먼저 큐의 동작에 대한 알고리즘 시간복잡도를 설명드리겠습니다.

 

동작	시간복잡도
Queue(삽입)	O(1)
Dequeue(제거)	O(N)
Find(탐색)	O(N)

 

즉, 위에서 구현한 알고리즘의 시간복잡도는 최대 O(N²)입니다. 여기서 더 좋은 알고리즘을 만들고자 실제 자료구조를 Queue와 같이 삽입과 제거 및 탐색을 반복해서 활용하지 않고, 아래와 같이 계속 문서 리스트를 순회하는 방법을 통한 알고리즘을 만들어보았습니다.

 

 

1. 인쇄 목록의 우선순위 리스트(priorities: 1~100)로, 실제 인쇄 목록에 있는 우선순위에 대한 목록(1~9)를 만든다.
2. 실제 인쇄 목록에 있는 우선순위의 목록을 내림차순으로 정렬한다.
3. 2번의 리스트를 순회하면서, 인쇄 목록 우선순위 리스트를 시작 Index부터 한바퀴씩 돌며 현재 출력할 수 있는 우선순위와 같은 문서를 출력하며, 순서를 카운트하고, 마지막에 출력한 Index를 기억한다.
4. 마지막 출력한 Index를 시작 Index로하여 3번을 반복한다.
5. 3~4번에 대해서 인쇄를 요청한 문서를 출력할 때까지 반복하며, 해당 순서를 반환한다.

 

 

뭔가 어려워 보이지만 실제 입력값으로 들어온 priorities의 입력 최대 크기인 100과 우선순위 최대 종류인 9는 효율성을 비교하기에 차이가 크지 않아 시간복잡도를 계산하기에 차이를 보이지 않을 수 있습니다. 하지만 입력 값에 대한 제한사항이 더 커질수록 심화과정에서 만들어진 알고리즘이 더 효율적인 것을 확인할 수 있으리라 생각합니다.

 

 

이 부분에 대한 코드 구현은 한번 직접 해보시기 바랍니다. 이 문제에 대한 답은 위에서 이미 구하였기에 이번 심화과정에서는 굳이 답을 도출하지 않을 것이며, 이번 심화과정은 알고리즘에 대한 효율성을 인지하고 공부하시는데 도움을 드리고자 함입니다. 그럼 심화과정에서 만들어진 알고리즘으로 구현한 코드는 댓글로 달아주시면 글을 읽는 분들에게 도움이 될 것이라 생각합니다.