[백준/BOJ] 11866번 : 요세푸스 문제 0 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

---

- 문제 -

 

난이도 실버 4 문제이다.

 

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

https://comain.tistory.com/225

[백준/BOJ] 1158번 : 요세푸스 문제 (JAVA / 자바)

위 문제랑 같다. 진짜 같다. 범위와 난이도만 다르다.

난이도가 한단계 더 높지만 더 쉬워보이는데 이유를 모르겠다.

 

그래서 이번엔 큐를 활용해 풀어보았다. 위 문제는 list를 사용해 나름 노가다 방식으로 풀었다.

이번엔 큐로 풀어보려 한다. 

1~ N까지 저장하고, 1부터 K-1번만큼 제외하고 다시 저장해준다. 그럼 K번째 값 전까지 제일 뒤로 옮겨질 것이다. 그리고 K번째 값을 제외 시킨다. 이 행동을 반복한다.

 

코드를 보자.

---

-풀이-

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		Queue<Integer> que = new LinkedList<Integer>();
		StringBuilder sb = new StringBuilder();
		
		for(int i = 1; i <= N; i++) {
			que.offer(i);
		}
		sb.append("<");
		while(que.size() > 1) {
			for(int i = 0; i < K; i++) {
				if(i == (K - 1)) sb.append(que.poll()).append(", ");
				else que.offer(que.poll());
			}
		}
		sb.append(que.poll()).append(">");
		System.out.println(sb);
	}
	
}

추가로 리스트로 푼 코드지만 요세푸스 문제와 위 코드와 다른 코드로도 풀어보았기에 올려보겠다.

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main{
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		List<Integer> list1 = new ArrayList<Integer>(Arrays.asList());
		
		StringBuilder sb = new StringBuilder();
		
		sb.append("<");
		
		for(int i = 1; i <= N; i++) {
			list1.add(i);
		}
		
		int i = 0;
		
        //N이 1이 될때까지 반복하는 반복문이다.
        //i를 인덱스 값으로 한다. N을 나누는 이유는 나온 인덱스 값이 리스트의 길이를 넘어가면 안되기 때문이다.
		while(N > 1){
			i = (i + (K - 1)) % N;
			sb.append(list1.remove(i)).append(", ");
			N--;
		}
		
		sb.append(list1.remove(0)).append(">");
		System.out.println(sb);
	}
}

---

-결과-

큐를 이용한 방식

리스트로 푼 방식

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.