코딩테스트 고득점 kit / 스택&큐 / 프린터 / JAVA

문제 https://programmers.co.kr/learn/courses/30/lessons/42587

---

풀이방법1 - Queue 2개 사용

import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        Queue<Integer> indexQ = new LinkedList<Integer>();
        Queue<Integer> valueQ = new LinkedList<Integer>();
        
        for(int i=0; i<priorities.length; i++){
            indexQ.offer(i);
            valueQ.offer(priorities[i]);
        }
        
        Arrays.sort(priorities);
        
        int i = priorities.length - 1;
        while(!indexQ.isEmpty()){
            
            if(priorities[i] == valueQ.peek()){
                valueQ.poll();
                if(location == indexQ.poll()) break;
                 i--;
                 answer++;
                
            } else {
                indexQ.offer(indexQ.poll());
                valueQ.offer(valueQ.poll());
            }
        }
        
        return answer+1;
    }
}

살짝 편법입니다.

index를 저장하는 큐와 우선순위 값을 저장하는 큐 두개를 만들어서 어떤 event가 발생하면 둘다 poll하거나 offer해서 짝을 맞춰주는 방식입니다. 이렇게 할 경우 따로 객체로 안묶어 줘도 된다는 점이 메리트 입니다.

 

priorities 배열을 역순 정렬한 이유는 큐를 돌면서 MAX값을 하나씩 차례대로 비교하기 위해서 입니다. 취향껏 stack을 섞어서 사용하셔도 되지만 쓸데없이 자료구조를 낭비하게 되므로 비추천 드립니다.

---

풀이방법 2 - Queue 1개 이용, location 활용 BEST

import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i=0; i<priorities.length; i++){
            q.offer(priorities[i]);
        }
        
        Arrays.sort(priorities);
        
        while(!q.isEmpty()){
            
            if(priorities[priorities.length - 1 -answer] == q.peek()){
                q.poll();
                answer++;
                if(location == 0) break;
            } else {
                q.offer(q.poll());
                if(location == 0) location = q.size();
            }
            
            location--;
        }
        
        return answer;
    }
}

location을 줄여가면서 인덱스의 위치를 확인하는 방법입니다.

만약에 location이 -1이 되면 다시 location이 큐의 끝을 가리키도록 하여

최종적으로 우선순위와 value값이 같고 location이 -1을 가리킬때 break 하도록 되어있습니다.

안드로이드 어댑터나 퀵정렬 등 평소 cursor 활용을 많이 하셨던 분들이라면 해당 방법으로 많이 접근하셨을것 같습니다.

 

풀이방법 3 - Array 2개 이용

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        int max = 0;
        int maxIndex = 0;
        int size = priorities.length;
        
        while(true){
            
            max = 0;
            
            for(int i=0; i<size; i++){
                if(max < priorities[i]){
                    max = priorities[i];
                    maxIndex = i;
                } 
            }
            
            if(maxIndex != 0) {
                int[] tmp = new int[maxIndex];
                
                for(int i=0; i<maxIndex; i++){
                    tmp[i] = priorities[i];
                }
                
                int j=0;
                for(j=0; j<size - maxIndex; j++){
                    priorities[j] = priorities[maxIndex+j]; 
                }
                
                for(int i=0; i<maxIndex; i++){
                    priorities[j++] = tmp[i];
                }
                
                location -= maxIndex;
            
                if (location < 0) {
                    location += size;
                }     
            }
            
            answer++;
            
            if(location == 0) break;
            
            for(int i=1; i<size; i++){
                priorities[i - 1] = priorities[i];
            }
            
            size--;
            location--;
        }
        
        return answer;
    }
}

배열로만 가지고 문제를 접근한 방법입니다.

프로그래머스 사이트의 Sujin lee 님의 아이디어입니다.

먼저 최댓값을 구하고 최댓값이 맨 앞에 있지 않으면 그 길이만큼 배열을 잘라서 뒤에다가 붙이는 방식입니다.

그 외 location을 감소시키면서 index를 찾는 부분은 동일합니다.

 

굉장히 배열에 대한 이해도가 뛰어난 코드라고 생각합니다.

정렬과 큐를 최댓값과 배열만 가지고 구현했다는 점에서 굉장히 창의적이고 멋진 코드 같습니다.

---

풀이방법 4 - 프린터 객체와 ArrayDeque이용

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

class Printers {
	
	private int index;
	private int value;

	public Printers(int index, int value) {
		this.index = index;
		this.value = value;
	}

	public int getIndex() {
		return index;
	}

	public int getValue() {
		return value;
	}
}

class Solution {
     public static int solution(int[] priorities, int location) {
		
		int answer = 0;
		
		Queue<Printers> q = new ArrayDeque<Printers>();
		for(int i=0; i<priorities.length; i++) {
			q.offer(new Printers(i,priorities[i]));
		}
		
		Arrays.sort(priorities);
		
		while(!q.isEmpty()) {
			if(q.peek().getValue() == priorities[priorities.length-1-answer]) {
				answer++;
				if(q.peek().getIndex() == location) break;
				q.poll();
			} else q.offer(q.poll());
		}
		
		return answer;   
     }
}

프린터 객체를 이용하여 큐에 집어넣을때 index와 우선순위값 둘다 넣어주는 방법입니다.

이전에 주식가격 문제풀때와 비슷한 방식으로 가장 생각하기 쉬운 방법입니다.

큐에 인덱스값을 같이 넣어주므로 해당 객체가 갖고있는 index값이 location과 같은지 비교해서 탈출하도록 만들어주면 됩니다.

 

추가적으로 ArrayDeque로 Queue를 만든이유는 LinkedList로 구현한 큐보다 성능이 더 좋기 때문입니다.

[알고리즘/알고리즘 Tip!] - [JAVA] 스택(Stack) vs 덱(Deque)

---

수행속도 비교(nanoTime) **동일한 테스트 케이스를 사용한 결과입니다.

	풀이방법 1	풀이방법 2	플이방법 3	풀이방법 4
1차 수행속도	747,500	685,600	6,400	928,500
2차 수행속도	707,800	714,100	6,700	998,600
3차 수행속도	685,100	729,000	6,700	1,042,000
평균	약 713.467	약 709,567	약 6,600	약 989,700

풀이방법 1,2는 거의 비슷한 속도이지만 메모리를 덜 사용한 풀이방법 2가 BEST라고 할 수 있겠습니다.

풀이방법 3 같은 경우에는 위의 결과와 같이 시간복잡도는 조금 떨어지나 데이터가 적다면 제일 빠르게 동작하게끔 되어있습니다.

풀이방법 4는 아무래도 객체를 사용해서 그런지 비교적 속도가 많이 뒤쳐지는 모습입니다.

---

히스토리

chucoding/algorithm