백준 1158번 요세푸스 제로베이스 자료구조 5일차 주제 : LinkedList

자료구조 1 Page 노트 정리 5일차 주제 : LinkedList

 

 

백준 1158번 : 요세푸스 문제 풀이

백준 1158번 문제

 

K번째 사람을 제거해야 하는데, index는 0부터 시작이니 K - 1 사람을 제거하는 문제다.예제에서는 K = 3 이니 index가 2인 사람을 계속해서 지워가면 된다.제거할 때마다 list의 size가 계속해서 줄어들기 때문에 index가 2인 사람이 존재하지 않을 수 있다.따라서 변수를 하나 생성하고 (int idx = 0;)idx + K - 1을 list.size()로 나눈 나머지를 이용해 삭제할 사람의 위치를 구해야 한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력을 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 출력을 위한 StringBuilder
        StringBuilder sb = new StringBuilder();

        // Stream을 이용한 배열 생성
        int[] inputData = Arrays
                .stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int N = inputData[0];
        int K = inputData[1];

        // Stream을 이용한 LinkedList 생성
        LinkedList<Integer> ll = IntStream
                .range(1, N + 1)
                .boxed()
                .collect(Collectors.toCollection(LinkedList::new));

        int idx = 0;
        sb.append("<");
        while (!ll.isEmpty()) {
            idx = (idx + K - 1) % ll.size();
            if (ll.size() != 1) {
                sb.append(ll.remove(idx)).append(", ");
            } else {
                sb.append(ll.remove(idx));
            }
        }
        sb.append(">");
        System.out.println(sb);

        br.close();
    }
}