[백준 | Java Silver IV] (#1158) 요세푸스 문제

문제

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

---

접근

ArrayList와 LinkedList는 거의 비슷하지만 ArrayList는 배열, LinkedList는 연결 리스트와 같은 개념으로 ArrayList는 삽입/삭제는 인덱스를 모두 이동해줘야해서 오래 걸리지만, 조회가 빠르다는 장점이 있다. 반면에 LinkedList는 삽입/삭제는 빠르지만, 조회가 상대적으로 오래걸린다. 

 

따라서 이 문제에서는 삭제를 계속해서 해줘야 하기 때문에 LinkedList를 선택해서 순열을 담아줬다. 

 

LinkedList에 담아둔 후, p를 둬서 인덱스를 k-1만큼 계속 옮겨주면서 삭제를 진행했다. 

 

 

 

첫번째 코드 - 성공

package week12.baek.july26.baek;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class S1158 {
    public static void main(String[] args) throws IOException {
        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 LinkedList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");
        int p = k-1;
        for (int i = 0; i < n; i++) {
            if(p > list.size()) p %= list.size();
            sb.append(list.get(p) + ", ");
            list.remove(p);
            p += k-1;
        }
        sb.deleteCharAt(sb.length()-1);
        sb.deleteCharAt(sb.length()-1);
        sb.append(">");

        System.out.println(sb.toString());
    }
}

 

최종 코드 - while문 사용으로 불필요한 코드 제거

 

package week12.baek.july26.baek;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class S1158 {
    public static void main(String[] args) throws IOException {
        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 LinkedList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");
        int p = 0;  // 시작 인덱스는 0
        while (!list.isEmpty()) {
            p = (p + k - 1) % list.size();  // 다음 제거할 인덱스 계산
            sb.append(list.remove(p)).append(", ");
        }
        sb.delete(sb.length() - 2, sb.length());  // 마지막 ", "를 제거
        sb.append(">");

        System.out.println(sb.toString());
    }
}