취업준비/알고리즘 문제 반추

프로그래머스 Level2 프린터. [상당히 애먹은 문제..] [ 나만의 풀이 ]

MoonTheKid 2021. 9. 9. 15:13

 

Queue의 활용보다는 도메인 로직이 더 까다로웠던 문제

 

문제가 언급한 규칙

 

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.

 

2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.

 

3. 그렇지 않으면 J를 인쇄합니다.

 

J를 인쇄하고 다시 1, 2, 3의 규칙이 진행된다.

 

EX. [2, 1, 3, 5, 4]라고 할 때

가장 중요한 우선순위를 가진 5가 나올때까지 앞에 모든 문서들은 뒤로 넘어간다.

=> [5, 4, 2, 1, 3]

이후 5를 프린트한다.

[ 4, 2, 1, 3]

4가 다음으로 우선순위가 높으므로 바로 프린트한다.

[2, 1, 3]

=> [1, 3, 2] => [3, 2, 1] 이 되며 순차적으로 3, 2, 1로 뽑히게 된다.

 

내가 해맸던 부분

우선순위가 가장 높은 문서를 뽑은후에 다시 규칙으로 돌아가는게 아닌 줄 알았다...

[ 제출 후 수많은 실패가 뜨고나서야 문제점을 확인했다. ] 

 

그리고 까다로운 부분인 location파트이다.

 

location의 경우 초기 세팅된 우선순위들에서 정하는 문서의 위치이다.

 

그리고 해당 문서의 위치한 우선순위가 몇 번째로 프린트되는지를 알아내야 한다. 

 

하지만 도메인 규칙에서 뒤에 존재하는 우선순위에 따라 몇 번째로 프린트 될지에 대해서는 정해진 바가 없다.

 

뽑은 문서의 order를 파악하고 이 값이 location과 같은지 비교하며 같은 경우 현재까지 프린트한 문서들의 수를 반환해야 몇 번째로 인쇄됐는지를 알 수 있는 것이다.

 

이에 대한 해결으로 순서와 우선순위를 가진 객체를 구성했다.

class Paper {
    public int priority;
    public int order;

    public Paper(int priority, int order) {
        this.priority = priority;
        this.order = order;
    }
}

 

진행 파트1 [ Deque 인터페이스로 Double Ended Queue를 생성한다. ]

Deque<Paper> queue = new ArrayDeque<>();
for(int i = 0; i < priorities.length; i++) {
  Paper paper = new Paper(priorities[i], i);
  queue.add(paper);
}

해당 인터페이스는 stack과 Queue 둘 다 가능한 좋은 인터페이스이다. 

 

사실 이 문제는 Queue 인터페이스로 풀어도 문제는 없다. [Deque 인터페이스는 Queue 인터페이스를 구현하고 있어 Queue의 API를 모두 지원한다 ] 

 

우선순위, index(order)의 값으로 큐에 모두 입력한다.

 

진행 파트2  [ 규칙 처리하기 ]

        int answer = 1;
        while(!queue.isEmpty()) {
            Paper curPaper = queue.peek();
            
            boolean canPrint = true;
            for(Paper p : queue) {
                if(curPaper.priority < p.priority) {
                    queue.add(queue.poll());
                    canPrint = false;
                    break;
                }
            }
            if(canPrint) {
                Paper printedPaper = queue.poll();
                if(location == printedPaper.order) return answer;
                answer++;
            }
        }
       return answer;
    }

1.CurrentPaper 즉 맨 앞에 있는 문서를 들여다본다(peek).

 

2. 그리고 이후의 Queue들의 값들을 순회(향상된 for loop)한다.

   a. 만약 현재의 문서의 우선순위보다 우선순위가 더 큰 문서가 있다면 해당 문서를 추출(poll)해서 뒤로 붙인다(add)

   b. 이 과정에서 canPrint 라는 플래그를 통해 현재 문서의 우선순위가 가장 큰지를 짚고 넘어간다. 

 

3. canPrint가 true이면 이후의 문서에서 우선순위가 더 높은 문서가 없다는 것이다. 가장 높은 우선순위의 문서를 출력(poll)한다. 이후 출력된 종이의 순서(order)값이 프로그램에 요청한 문서의 위치(location)과 동일한지 체크한다.

동일한 경우라면 바로 answer를 반환한다. 

그렇지 않은 경우라면 출력한 종이의 양을 1 증가시킨다. [ 지금 보니.. answer라는 변수명이 조금 아쉽다. ]

 

4. 그렇게 큐가 빌때까지 반복한다.

[ 이 문제는 마지막 return에 도달하지 못한다. ]

 

[ 전체 코드 코드의 가독성을 위해서 변수명을 좀더 향상해봤다. ]

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {

        Deque<Paper> queue = new ArrayDeque<>();
        for(int order = 0; order < priorities.length; order++) {
            Paper paper = new Paper(priorities[order], order);
            queue.add(paper);
        }
        
        int printPaperCount = 1;
        while(!queue.isEmpty()) {
            Paper curPaper = queue.peek();
            
            boolean canPrint = true;
            for(Paper p : queue) {
                if(curPaper.priority < p.priority) {
                    queue.add(queue.poll());
                    canPrint = false;
                    break;
                }
            }
            if(canPrint) {
                Paper printedPaper = queue.poll();
                if(location == printedPaper.order) return printPaperCount;
                printPaperCount++;
            }
        }

        return printPaperCount;
    }
    
    class Paper {
        public int priority;
        public int order;

        public Paper(int priority, int order) {
            this.priority = priority;
            this.order = order;
        }
    }
}

 

개인적인 생각

확실히 문제의 규칙을 빠삭하게 이해하는게 중요한 것 같다.

 

해당 문제는 Level2인데 나에겐 상당히 까다롭게 느껴진 문제였다. [ 다른 Level2도 다 어렵지만.. 같은 Level2에서도 더 어렵게 느껴진 문제였다. ]

객체형태의 구조를 갖추지 않았다면 풀 엄두가 나질 않았을 것 같다.

 

 

반응형