백준1158_요세푸스 문제 (java)

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

1158번: 요세푸스 문제

문제 풀이 방식

1. 처음생각
   • 처음에는 3번째 마다 제거한다고 해서 n까지의 for문에서 index를 증가시키면서 출력하려고 했으나, 단순히 인덱스만 증가시키면 n다음에 1로갈 수 있는 방법이 떠오르지 않음.
2. 다음생각
   • 문제에서 사람들이 원을 이루어 앉아있다고 하였기에 단순히 원형큐 자료구조를 사용하려고 했음.
   • 그러나, 앞에서는 데이터를 뽑거나 삭제하는 일만 일어나고 뒤에서는 앞에서 뽑은 데이터를 넣기만 하면되기 때문에 일반적인 큐 자료구조를 써도 되겠다고 생각하였다.

수도코드 

해당문제는 수도코드로 간단하게 나타내보았기에 백준에 제출해도 성공이뜨지는 않는다!

Queue<String> que = new LinkedList<String>();
int n = input();
int k = input();
int[] arr = new int[n];

for(int i=0; i<n; i++) que.add(i);

function String josephus() 
	sb.append("<");
	int cnt = 0
	
	while(true) {
		if(que.size ≥ k) // 큐 사이즈가 k값보다 같거나 커야 k번째까지 add, poll할 수 있다.
			cnt++; 
			if(cnt != k) que.add(que.poll()) // k번째 전 큐의 앞에 값을 뒤로 보냄
			else 
				sb.append(que.poll() + ", ") // cnt == k이면 k번째 수라는 뜻이므로 출력(제거)
				cnt = 0 // 다시 k번째 수를 뽑아야하니까 cnt를 초기화

		else if(que.size < k && !que.isEmpty) // 큐의 사이즈가 k값보다 적고, 큐가 비어있지않을때
			if(que.size == 1) // 마지막 수는 > 괄호를 붙여서 출력.
				sb.append(que.poll() + ">);
				return sb

			sb.append(que.poll() + ", ")
	}
	return sb

 

시간복잡도 분석 O(N)

Queue<String> que = new LinkedList<String>();
int n = input();
int k = input();
int[] arr = new int[n];

for(int i=0; i<n; i++) que.add(i); // O(n)

function String josephus() 
	sb.append("<");
	int cnt = 0
	
	while(true) { // O(n)
		if(que.size ≥ k) 
			cnt++; 
			if(cnt != k) que.add(que.poll()) 
			else 
				sb.append(que.poll() + ", ") 
				cnt = 0 

		else if(que.size < k && !que.isEmpty) 
			if(que.size == 1)
				sb.append(que.poll() + ">);
				return sb

			sb.append(que.poll() + ", ")
	}
	return sb

 

 

 

저도 배워가는 중이므로 혹시나 잘못된 부분이 있으면 피드백 환영입니다~~