BOJ) 요세푸스 문제

요세푸스 문제

1158번: 요세푸스 문제

풀이

 

쉽게 봤던 문제였는데, 푸는데 약간의 시간이 들었다.

이미 테이블에서 빼낸 사람을 건너 뛰면서 k번 째 사람을 빼내야 하는 문제에서, 여러 명이 빠져있는 경우에 새롭게 빼내야하는 사람을 어떻게 구해야하는지 생각하는데 시간이 조금 걸렸다.

 

그래서 결국, k번 째 까지 갈 때, 이미 빠져있는 사람이 있으면 총 가야하는 횟수에 +1을 증가시키면서 자리를 탐색했다.

맞기는 했지만, 배열을 이용해서 하니까 탐색 시간이 너무 많이 걸렸다.

 

그래서 List로 바꿔서 풀어보기로 했다.

List에서 k번 째 있는 사람을 빼내는 동시에 list에서 제거해주니까 너무 쉽게 풀렸다.

속도도 훨씬 빨랐기 때문에, List로 푸는 것을 추천한다.

 

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class CycleSeat_1158 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        solution(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));

        br.close();
    }

    private static void solution(int n, int k) {  
        int[] table = getTable(n);
        int[] visit = new int[n];
        int idx =-1;
        StringBuffer sb = new StringBuffer("<");
        final String restSign = ", ";
        for(int i=0; i<n; i++) {
            int cnt=k;
            for(int j=0; j<cnt; j++) {
                idx=(idx+1)%n;
                if(visit[idx] ==1) {
                    cnt++;
                }
            }
            visit[idx] =1;
            sb.append(table[idx]).append(restSign);
        }
        sb.deleteCharAt(sb.length()-1);
        sb.setCharAt(sb.length()-1, '>');
        System.out.println(sb.toString());
    }
    private static int[] getTable(int n) {
        int[] result = new int[n];
        for(int i=0; i<n; i++) {
            result[i] = i+1;
        }
        return result;
    }
}

 

코드 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class CycleSeat_1158 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        solution(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));

        br.close();
    }

    private static void solution(int n, int k) {    // 훨씬 효율적
        ArrayList<Integer> tableList = new ArrayList<>();
        StringBuffer sb = new StringBuffer("<");
        final String restSign = ", ";

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

        int idx =0;
        while(!tableList.isEmpty()) {
            idx = (idx+k-1)%n;
            sb.append(tableList.get(idx)).append(restSign);
            tableList.remove(idx);
            n--;
        }
        sb.deleteCharAt(sb.length()-1);
        sb.setCharAt(sb.length()-1, '>');
        System.out.println(sb.toString());
    }
}