자료구조-프린터 큐 문제

Seok·2022년 1월 25일
0
post-thumbnail

문제풀이

이 문제는 큐를 응용하는 문제로 N개의 문서 중 중요도에 따라 높은 것 순으로 출력해야하는 문제이다. 문제를 풀기 전 어떤 형태의 알고리즘으로 풀어야 할지 분석하였다.

  1. 0번째 부터 순서대로 입력을 받아 큐에 넣어준다.
  2. 큐에는 순서 index와 중요도를 int 배열로 삽입한다.
  3. 맨 앞 인덱스의 중요도를 Pop하여 나머지 중요도의 크기와 비교하고 중요도가 더 큰 것을 큐의 맨 앞으로 오게하고 count를 증가 시킨다.
  4. 큐의 맨 앞의 인덱스가 M의 값과 같은지 비교한다.
  5. 값이 다르면 다시 반복문을 돌리고 값이 같다면 break를 하여 count의 개수를 출력한다.

소스 코드

package data_structure;

import java.util.*;

public class print_queue {

public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner in = new Scanner(System.in);
	
	StringBuilder sb = new StringBuilder();
	
	int n = in.nextInt();
	
	for(int i = 0; i<n; i++) {
		int N = in.nextInt(); // 총 문서 개수
		int M = in.nextInt(); // 원하는 문서 위치 값
		
		LinkedList<int[]> que = new LinkedList<>();
		int count = 0;
		
		for(int j = 0; j<N; j++) {
			que.offer(new int[] {j, in.nextInt()} );
		}
		
		while(!que.isEmpty()) {
			int[] first = que.poll();
			boolean isMax = true;
			
			for(int z = 0; z<que.size(); z++) {
				if(first[1] < que.get(z)[1]) {
					que.offer(first);
					for(int j = 0; j<z; j++) {
						que.offer(que.poll());
					}
					isMax = false;
					break;
				}
				
			}
			if(isMax == false) {
				continue;
			}
			
			count++;
			if(first[0] == M)
				break;
		}
		
		sb.append(count).append("\n");
		
	}
	System.out.print(sb);
	
}

}

문제를 풀고 느낀점

  • 큐의 응용문제라 쉽게 풀 수 있을거라 생각했지만 우선 어떻게 알고리즘을 설계하여할지 감이 도통 잡히지 않아 구글링을 통해 다양한 방법을 배웠고, 그 중 나와 가장 비슷하게 구현을 시도했던 코드를 참조하여 문제를 풀었다. 이번 응용 문제를 통해 큐에 대해 완벽히 숙지할 수 있는 시간이었던 것 같다.
profile
네이티브 앱개발에 관심많은 주니어 개발자

0개의 댓글