Today's Algorithm(2018-10-16)

programmers 프린터

오늘도 스택 카테고리에 있는 문제를 풀었습니다. 프린터 문제인데요. 이 문제를 풀면서 어려웠던 점이나 고민되었던 점을 간략하게 정리하겠습니다.

 

• (처음 위치, 바뀐 위치, 우선순위) 이렇게 3가지 정보를 어떻게 자료구조에 담을 것인가?

  • 이 부분이 이 문제에서 가장 고민되었던 부분입니다. 기본적으로 프린터의 구조상 Queue형태로 문제를 풀어나가야 한다는 것은 알겠지만 여기에 어떤 자료형을 담을지, 그리고 answer로 제출할 답들은 어디에 넣을지가 고민되었습니다.

  • 결국 Job이라는 내부 클래스를 만들어 자료형으로 만들어야 겠다는 생각이 들었습니다. 전에 C++할때는 Pair라는 자료구조가 있어서 동시에 2개 정보를 담을 수 있었지만 자바에선 이런게 없었기 때문입니다.

    class Job {
        int priorities;
        int position;
    
        public Job(int priorities, int position) {
            this.priorities = priorities;
            this.position = position;
        }
    }
    

  • 따라서 스택엔 Job이라는 자료구조를 넣고 이 안에서 (우선순위, 원래위치) 값을 가지고 있습니다. 그리고 스택에서 빠져나오는 값(출력되는 작업)은 List<Integer>형으로 차례대로 '원래위치' 값을 넣었습니다. 빼낼 때는 IndexOf를 사용하면 해당 값에 대한 인덱스를 얻어 바뀐 위치를 알 수 있습니다.

• Queue는 어떻게 구현하나?

  • 두번째의 관문은 C++와 다른 Queue의 구조였습니다. Queue는 인터페이스이기 때문에 큐를 구현한 클래스로 객체 생성을 해야하는데요. 종류로는 LinkedList, priorityQueue, priorityBlockingQueue가 있다고 합니다. 저는 이 중에서 LinkedList를 사용하여 구현하였습니다.

  • 자바에서 제공하는 Queue관련 메서드는 아래와 같습니다.

    public void offer(Element data);  // 순차보관(뒤에 넣기)
    public Element poll();   // 가장 먼저 보관한 값 꺼내고 반환(젤 앞에 것 꺼내기)
    public Element peek();   // 가장 먼저 보관한 값 단순 참조, 꺼내지 않음(젤 앞 값만 보기)
    public boolean empty();  // 비어있는지 판별
    

 

모두 구현한 코드는 아래와 같습니다.

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<Job> queue = new LinkedList();
        List<Integer> answerArray = new ArrayList<>();

        for (int i = 0; i < priorities.length; i++) {
            queue.add(new Job(priorities[i], i));
        }

        while(!queue.isEmpty()) {
            boolean pass = true;
            Job firstJob = queue.poll();
            for (Job job : queue) {
                if(job.priorities > firstJob.priorities) {
                    queue.offer(firstJob);
                    pass = false;
                    break;
                }
            }
            if(pass) {
                answerArray.add(firstJob.position);
            }
        }

        return answerArray.indexOf(location) + 1;
    }
}

class Job {
    int priorities;
    int position;

    public Job(int priorities, int position) {
        this.priorities = priorities;
        this.position = position;
    }