프린터

---

프로그래머스 코딩테스트 연습 - 프린터

 

다음과 같은 과정을 거치는 프린터를 구현하는 문제

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼낸다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣는다.
3. 그렇지 않으면 J를 인쇄한다.

 

parameters

• priorities: 현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 
• location: 현재 대기목록의 내가 인쇄를 요청한 문서 위치

 

return

• 내가 인쇄를 요청한 문서의 인쇄 순서

 

---

나의 풀이

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<Document> queue = initialQueue(priorities);
        List<Integer> list = new ArrayList<Integer>();
		
        while(queue.size()>0) {
            Document first = queue.poll();
			
            if(haveBiggerNum(queue, first)) {
                queue.add(first);
            } else {
                list.add(first.getDocId());
            }
        }
        return list.indexOf(location)+1;
    }
	
    public Queue<Document> initialQueue (int[] arr) {
        Queue<Document> queue = new LinkedList<Document>();
        int len = arr.length;
		
        for(int i=0;i<len;i++) {
            queue.add(new Document(i,arr[i]));
        } return queue;
    }
	
    public Queue<Document> cloneQueue (Queue<Document> q) {
        Queue<Document> queue = new LinkedList<Document>();
        queue.addAll(q);
        return queue;
    }
    
    public boolean haveBiggerNum(Queue<Document> q, Document first) {
        int firstPri = first.getPriority();
        Queue<Document> queue = cloneQueue(q);
        while(queue.size() > 0){
            int nowPri = queue.poll().getPriority();
            if(nowPri > firstPri) return true;
        } return false;
    }
	
    private static class Document {
        private int docId;
        private int priority;
		
        Document(int docId, int priority) {
            this.docId = docId;
            this.priority = priority;
        }

        private int getPriority() {
            return this.priority;
        }
		
        private int getDocId() {
            return this.docId;
        }
    }
}

java의 '얕은 복사', '깊은 복사'를 눈치 못채서 푸는데 엄청 오래 걸렸다...

처음에는 println 로그만 찍었는데 이상하게 값이 너무 많이 삭제되어서 왜이럴까? 싶어서 Eclipse로 소스 옮기고 디버그 찍기 시작했다

haveBiggerNum() 메소드에서 남은 요소 중에서 더 큰 수가 있나 찾아볼때 삭제가 이루어지다보니 solution 메소드의 while문 한 번 돌때 한 번 삭제가 아닌 여러번 삭제가 된거였다....

 

깊은 복사와 얕은 복사 예전에 학교에서 배웠던거긴 한데...

정말 오랜만에 들은 개념이라 솔직히 잊고 있었다.

깊은 복사와 얕은 복사 공부 ☞ https://yeonyeon.tistory.com/122

 

while문을 너무 많이 돌아서 아쉬운 점이 많은 풀이 방식이긴 하다.

 

---

다른 사람 코드

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        int l = location;

        Queue<Integer> que = new LinkedList<Integer>();
        for(int i : priorities){
            que.add(i);
        }

        Arrays.sort(priorities);
        int size = priorities.length-1;

        while(!que.isEmpty()){
            Integer i = que.poll();
            if(i == priorities[size - answer]){
                answer++;
                l--;
                if(l<0)
                    break;
            }else{
                que.add(i);
                l--;
                if(l<0)
                    l=que.size()-1;
            }
        }
        return answer;
    }
}

돌아가는 원리는 그림 그려보면서 하니까 알긴 하겠는데 어떻게 이런 로직을 생각하셨는지는 잘 모르겠다...

 

배열에는 프린터에 출력되어야 하는 순서대로 정렬된다.

2, 4, 2, 3이라는 배열이 있다면 4, 3, 2, 2 순으로 출력되어야 한다.

 

배열의 인덱스가 0 ... n 이라면 size는 n이고, answer은 0부터 1씩 커진다.

size와 answer는 배열의 인덱스를 찾기 위해 이용하는 변수가 되고

location을 복사한 l은 queue를 순회하기 위해 이용하는 변수가 된다.

 

queue의 요소가 전부 사라질 때까지 while에서 순회하는데,

  Queue를 돌면서 배열의 특정 요소(size-answer)와 동일한 값이 있으면 제거하고, answer 값을 1 늘린다.

  동일한 값이 아닌 경우에는 Queue의 맨 끝에 요소를 추가한다.