[알고리즘] 큐 문제 풀이(백준 10845번, 1158번, 1966번)

1. 큐(백준 10845번)

 

10845번: 큐 (acmicpc.net)

10845번: 큐

 

▷ 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class QueueEx {
	
	public static void main(String args[]) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
				
		Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용

		int num = Integer.parseInt(br.readLine());
		
		int last = 0;
			
		for(int i=0; i<num; i++) {
			String behav[] = br.readLine().split(" ");
			
			switch (behav[0]) {
			case "push": 
				last = Integer.parseInt(behav[1]);
				queue.add(last);
				break;
			case "pop" : 
				sb.append(queue.isEmpty()?-1:queue.poll()).append("\n");
				break;
			case "size" : sb.append(queue.size()).append("\n");
				break;
			case "empty" : sb.append(queue.isEmpty()?1:0).append("\n");
				break;
			case "front" : sb.append(queue.isEmpty()?-1:queue.peek()).append("\n");
				break;
			case "back" : sb.append(queue.isEmpty()?-1:last).append("\n");
				break;
			}
		}
		System.out.println(sb);

	}
}

 

 

2. 요세푸스 문제(백준 1158번)

 

 

1158번: 요세푸스 문제 (acmicpc.net)

1158번: 요세푸스 문제

 

▷ 풀이 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Josephus {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int k = sc.nextInt();
		
		Queue<Integer> queue = new LinkedList<>();
				
		for(int i=1; i<=n; i++) {
			queue.add(i);
		}
		
		String answer = "<";
		
		for(int i=0; i<n; i++) {
			for(int j=1; j<k; j++) {
				queue.add(queue.poll());
			}
			answer += queue.poll();
			if(i != n-1) answer += ", ";
		}
		
		answer += ">";
		
		System.out.println(answer);

		
	}
}

 

 

3. 프린터 큐 문제(백준 1966번)

 

1966번: 프린터 큐 (acmicpc.net)

1966번: 프린터 큐

 

▷ 풀이 코드

import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class PrinterQueue {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
	
		for(int i=0; i<num; i++) {
			
			int n = sc.nextInt();
			int m = sc.nextInt();
			
			Queue<Integer> queue = new LinkedList<>(); // 중요도
			Queue<Integer> numQue = new LinkedList<>(); // 인덱스

			for(int j=0; j<n; j++) {
				queue.add(sc.nextInt());
				numQue.add(j);
			}
			
			int cnt = 0;
			
			while(!queue.isEmpty()) {
				int max = Collections.max(queue);
				int idx = numQue.poll();
				int now = queue.poll();
				
				if(now == max) {
					cnt++;
					if(idx == m) {
						System.out.println(cnt);
						break;
					}
					
				} else {
					numQue.add(idx);
					queue.add(now);
				}
				
			}
		}
	}
}

 

이번에는 알고리즘 스터디에서 공부했던 Queue(큐)를 통해 백준 문제 풀이를 해보았습니다!!

 

Queue 의 원리에 대해서는 이해하지만 이 것을 실제로 적용해보려니 좀 어렵네요

 

더 다양한 문제들을 풀어보면서 문제 풀이 방법들에 대해서 익혀볼게요~

 

많은 분들의 피드백은 언제나 환영합니다!  많은 댓글 부탁드려요~~