백준 1158(요세푸스 문제) - Python(파이썬),Java(자바) - 자료구조(큐)

1158번: 요세푸스 문제

예제 설명

---

이걸 좀 해석하면

---

① 제일 앞에 있는 값을 pop하고 뒤에다가 append한다

② 그 과정을 두번 하고나서 

③ 세번째에는 pop하면서 나오는 값을 따로 큐에 저장한다.

이렇게 세 개의 과정을 한번 할때마다 하고서 큐에 사람 수만큼 채워지면 그만둔다.

 

풀이과정

① 사람 수만큼 1번부터 사람수까지 번호를 부여한다.
② 제일 앞에 있는 값을 pop하고 다시 append에서 뒤로 붙이는 과정을 두번을 하므로 range(2)만큼 for문을 실행한다. 
③ 세번째 pop하는 것은 visted 리스트에 붙인다.
④ ②,③번의 과정을 모두 큐에 저장할 때까지 반복한다.

💻 Python(파이썬)

import sys
from collections import deque
#사람수, 제거되는 사람 번호
n,k = map(int,sys.stdin.readline().split())
#사람 리스트 - 1번부터 n번까지
q = deque(range(1,n+1))
#나올 사람 리스트
visted =[]

while q:
    for i in range(k-1):
    	#큐에서 Pop하고 뒤에 다시 붙이기
        q.append(q.popleft())
    #세번재 pop하는건 따로 리스트에 저장
    visted.append(q.popleft())

print("<",", ".join(str(i) for i in visted),'>',sep="")

💻 Java(자바)

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

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()," ");
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        Queue<Integer> q = new LinkedList<>();
        for(int i=0;i<n;i++){
            q.offer(i+1);
        }
        sb.append("<");
        while(!q.isEmpty()){
            for(int i=0;i<k-1;i++){
                q.offer(q.poll());
            }
            if(q.size()!=1){
                sb.append(q.poll()).append(", ");
            }else{
                sb.append(q.poll());
            }
        }
        sb.append(">");
        System.out.println(sb);
    }
}