[PS] BOJ1158 요세푸스 문제 ( 자료구조 ) with Python,JAVA

 

◎ 문제

1158번: 요세푸스 문제

 

 

◎ 문제플이

 

큐 자료구조를 활용하면 쉽게 풀리는 문제이다. 

 

1) 1부터 N까지 큐에 PUSH한다. 

2) K번째 수를 찾으면 POP한다.

3) K번째 수가 아니면 POP하고 다시 PUSH한다. 

 

 

◎ 코드

 

Python

from collections import deque
import sys
input = sys.stdin.readline

n,k = map(int,input().split())
q = deque([ x for x in range(1,n+1)])
result = []

count = 1 
while q :
  if count == k :  # K번째이면 POP하기
    result.append(q.popleft())
    count = 1
  else : # K번째가 아니면 POP하고 다시 PUSH하기
    q.append(q.popleft())
    count += 1

print("<",", ".join(list(map(str,result))),">", sep='') # sep='' 공백을 없애고 ", " 구분자로 출력하기

 

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        Queue<Integer> queue = new LinkedList<>();

        for(int i = 1;i<=n;i++){
            queue.add(i);
        }

        int count = 1;
        List<Integer> result = new ArrayList<>();
        while(!queue.isEmpty()){
            if( count == k ){
                result.add(queue.remove());
                count = 1;
                continue;
            }
            queue.add(queue.remove());
            count++;
        }

        sb.append("<");
        for (int i = 0; i<result.size();i++) {
            if( i == result.size()-1) {
                sb.append(result.get(i)).append(">");
            }else{
                sb.append(result.get(i)).append(", ");
            }
        }
        System.out.println(sb);
    }
}