[BaekJoon] 1158번 요세푸스 문제 풀이 (Success)

1158번: 요세푸스 문제

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        List<Integer> list = new ArrayList<>();
 
        for (int i = 0; i < N; i++) {
            list.add(i + 1);
        }
 
        StringBuffer sb = new StringBuffer();
 
        int idx = 0;
        for (int i = 0; i < N; i++) {
            idx = idx + K - 1 > list.size() ? idx + K - 1 - list.size() : idx + K - 1;
            while (idx >= list.size()) {
                idx = idx - list.size();
            }
            sb.append(list.get(idx));
            if (i != (N - 1)) {
                sb.append(", ");
            }
            list.remove(idx);
        }
 
        bw.write("<" + sb + ">");
 
        bw.flush();
        bw.close();
 
    }
 
}
 

🤔 해설

1. for (int i = 0; i < N; i++) { ... }

    - list에 1부터 N까지 대입

 

2. idx = idx + K - 1 > list.size() ? idx + K - 1 - list.size() : idx + K - 1;

    - 배열은 0부터 시작하므로 (K-1)값을 기준으로 확인

        - list 크기보다 크면 list를 이미 한바퀴 순회한 것으므로 list 크기만큼 빼주기

        - list 크기보다 작으면 그대로 idx에 K-1 더하기

 

3. while (idx >= list.size()) { ... }

    - idx가 list 사이즈보다 크지 않게 반복문 실행

 

4. sb.append(list.get(idx));

    - list에서 K 위치값(배열의 위치이므로 K-1값) 호출

 

5. if (i != (N - 1)) { ... }

    - 마지막 값이 아닐 경우에만 반점(,) 추가

 

6. list.remove(idx);

    - list idx값 호출 후 제거

 

😮 이 외의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        Queue<Integer> queue = new LinkedList<>();
 
        for (int i = 0; i < N; i++) {
            queue.add(i + 1);
        }
 
        StringBuilder sb = new StringBuilder("<");
 
        while (queue.size() > 1) {
            for (int i = 0; i < K - 1; i++) {
                queue.add(queue.poll());
            }
            sb.append(queue.poll() + ", ");
        }
 
        sb.append(queue.poll() + ">");
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
}
 

1. queue.add(queue.poll());

    - poll(): queue의 첫 번째 요소 출력 및 제거

    - queue.add(...): K 이전의 숫자 제거 후, K 이후에 재 입력

 

2. sb.append(queue.poll() + ", ");

    - K번째 숫자 출력 및 제거

 

3. sb.append(queue.poll() + ">");

    - size가 1일 때는 queue 마지막 요소 출력 및 제거

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

[BOJ] 백준 1158번 : 요세푸스 문제 (JAVA)