[Queue/구현] 백준 11866번 요세푸스 문제 0 - JAVA (반복문/큐 2가지 풀이)

 

백준 에센셜 문제로 나와있는 요세푸스 문제 0를 풀어보았다.

 

원래는 큐 문제인데, 나는 구현문제라고 보고 일단 풀어보았다.

그 뒤에 다른 분의 설명을 보면서 다시 큐로 풀어보았다.

 

2가지 풀이법, 입맛에 맛게 준비했다!

 

실버 5문제인데, 생각보다 어려웠다 ㅠ ㅠ

 

 

---

1. 문제 출처

---

 

 

11866번: 요세푸스 문제 0

 

import 깔끔하게 정리하고 2번 제출했던 문제

 

 

---

2. 설계

---

 

1. 첫 시작은 K(제거할 순서)부터 시작한다.

예를 들어 K=3이면 3번째 사람부터 제거한다.

int targetNum=K;

 

 

2. 단순히 K만큼 가서 % N을 해주는 방식은 안된다.

예를 들어 N=7 K=3일 때, 3 -> 6 -> 9(9%7=2) -> 5 -> 1 -> 4 -> 7이 나오게 되는데 이는 답이 아니다.

<3, 6, 2, 7, 5, 1, 4>

 해당 답을 도출하기 위해선 K칸을 갈 때 이미 나온 숫자는 걸러서 가야한다.

그를 위해 while문을 사용해 선택되지 않은 숫자 K만큼 갈 때까지 돌게 한다.

int jump=0;
int targetNum=K;
		
for(int i=0;i<N;i++) {
	if(i==N-1) {
		System.out.printf(targetNum+">");//마지막은 따옴표 생략
	}
	else System.out.printf(targetNum+", ");
	
    index[targetNum]=true;//첫숫자를 이미 뽑힌 숫자로 체크
	
    //뽑힌 숫자가 아닌 K개의 숫자를 거칠 때까지 반복을 돈다.		
	while(jump!=K && i!=N-1) {
		targetNum=(targetNum+1)%N;//다음 숫자를 타겟숫자로 잡는다.
		if(targetNum==0)targetNum=N;//타겟 숫자가 0이면 N으로 바꿔준다.
		if(index[targetNum]==false) jump++;//타겟숫자가 아직 뽑히지 않은 수면 채택한다.
	}
	jump=0;//다음 턴을 위해 초기화한다.
}

i가 N-1번으로 들어왔을 때 마지막 targetNum을 출력하고, while로 오기 때문에 while문을 돌려줄 필요가 없다. 이미 출력한 상태에서 문제해결이 완료되었기 때문이다. 

 

 

---

3. 전체 코드

---

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc =  new Scanner(System.in);
		
		int N = sc.nextInt();//1~N명의 사람
		int K = sc.nextInt();//K번째 사람 제거
		
		boolean[] index = new boolean[N+1];
		
		System.out.printf("<");
		
		int jump=0;
		int targetNum=K;
		
		for(int i=0;i<N;i++) {
			if(i==N-1) {
				System.out.printf(targetNum+">");
			}
			else System.out.printf(targetNum+", ");
			index[targetNum]=true;
			
			while(jump!=K && i!=N-1) {
				targetNum=(targetNum+1)%N;
				if(targetNum==0)targetNum=N;
				if(index[targetNum]==false) jump++;
			}
			jump=0;
		}
	}

}

 

 

---

4. 다른 풀이 (Queue)

---

 

 

[백준] 11866번 : 요세푸스 문제 0 - JAVA [자바]

 

이 분 블로그를 보고, 큐로 푸는 방법을 단박에 알 수 있었다. 빼내고, 다시 넣는 작업이 포인트였다.

 

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

public class Main {

	public static void main(String[] args) {
		Scanner sc =  new Scanner(System.in);
		
		int N = sc.nextInt();//1~N명의 사람
		int K = sc.nextInt();//K번째 사람 제거
		
		Queue<Integer> q = new LinkedList<>();
		
		//1~N까지 사람 데이터 주입
		for(int i=1;i<=N;i++) {
			q.add(i);
		}
		
		//K번째 사람 제거 실시
		//큐가 모두 비었다는 것은 모든 사람이 제거되었다는 것을 의미한다.
		System.out.printf("<");
		while(!q.isEmpty()) {			
			//K번째있는 사람을 맨 앞으로 데려오기
			//K-1명의 사람을 맨뒤로 보내면 K번째 사람이 나온다.
			for(int i=0;i<K-1;i++) {
				int cur=q.poll();//1 나오고 -> 2 나오고
				q.add(cur);//1 맨뒤로 직행 -> 2 맨뒤로 직행
			}
			if(q.size()==1) System.out.printf(q.poll()+">");//3 출력
			else System.out.printf(q.poll()+", ");//3 출력
		}	
	}
}

메모리와 시간 더 쓰고 통과 ^^

 

---

Queue 기초 다지기 성공 ~ !