Java 스택, 큐 알고리즘4 + 빠른 입출력

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

Queue

줄을 지어 순서대로 처리된다. FIFO의 형태를 가진다.

import java.util.LinkedList;

import java.util.Queue;

둘 다 import 해야 사용 가능하다.

 

Enqueue : 큐 맨 뒤에 데이터를 추가한다.

Dequeue : 큐 맨 앞쪽의 데이터를 삭제한다.

큐 한 쪽 끝을 front로 정하여 삭제 연산만 수행한다. 다른 한 쪽은 rear로 정해 삽입 연산만 수행한다.

그래프의 넓이 우선 탐색(BFS)에서 사용한다.

 

Queue 사용하기

Queue<Integer> queue = new LinkedList<>();

 

Queue에 값 추가하기

queue.offer(1);

 

Queue 값 삭제하기

queue.remove(); // 첫 번째 값 제거하기
queue.poll(); // 첫 번째 값 반환하고 제거하기, 비어있다면 null 반환한다.
queue.clear(); // queue 초기화하기

 

 

 

문제 6 :

첫 줄에 자연수 n(5<=n<=1000)과 k(2<=k<=9)가 주어진다.

n명의 왕자가 1부터 n번까지 시계방향으로 동그랗게 앉는다.

1번 왕자부터 시계방향으로 돌아가며 1부터 시작해 번호를 외치고,

한 왕자가 k를 외치면 그 왕자는 원 밖으로 나오게 된다.

그리고 다음 왕자부터 다시 1부터 시작해 번호를 외친다.

마지막까지 남아있게 되는 왕자 번호를 출력하는 프로그램을 작성하시오.

 

소스코드 :

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;

class Main {
	public int solution(int n, int k) {
		int answer = 0;
		Queue<Integer> Q = new LinkedList<>();
		for(int i=1; i<=n; i++) Q.offer(i);
		int t = n;
		while (t > 1) {
			// k번째 숫자가 삭제되면 그 다음 숫자로 가니까 int i=1 부터 시작
			for(int i=1; i<k; i++) Q.offer(Q.poll());
			Q.poll();
			t--;
		}
		answer = Q.poll();
		return answer;
	}

	public static void main(String[] args) throws IOException {
		Main T = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		bw.write(String.valueOf(T.solution(n, k)));
		bw.flush();
		bw.close();
	}
}

 

풀이 :

Queue에 인덱스가 없으므로 Q.offer(Q.poll());로 구현했다.

 

 

 

 

BufferedReader, Tokenizer, BufferedWriter 이용해서 빠른 입출력으로 코드를 구현하였다.

readLine()시 리턴값 String으로 고정되기 때문에 다른 타입으로 입력 받기 위해선 형변환을 해주어야 한다.

예시 ) int t = Integer.parseInt(br.readLine());

bw.write도 마찬가지로 int형일 경우 String.valueOf 이용해 string으로 바꿔준다.

import java.util.*;

import java.io.*;

로 해도 되는데 하나하나 입력해봤다.

아마 다음부턴 평소에 쓰던 입출력 코드를 작성할 것 같다..