Josephus문제푸는데 시간 초과

  • qkrqudwn
    qkrqudwn

    아래의 코드로 문제를 해결했습니다. 큐를 이용하여
    이클립스로 문제를 돌려보니 답안이 맞는걸 확인할수 있었습니다.
    시간초과로 답이 맞는지 확인을 못했는데 시간을 단축시킬수 있는 방법이 있을까요 ? 제 생각에 이문제를 푸는데 큐를 이용하는 것이
    최적의 방법이라 생각되었습니다.

    import java.util.Scanner;

    public class jose {
    static int array[] = new int[1000];

    public static void function(int N, int K) {
    
        for (int i = 0; i < N; i++) {
            array[i] = i + 1;
        }
    
        deque();
    
    
        while (!check()) {
            for (int i = 0; i < K; i++) {
                if (i == K - 1) {
                    deque();
                    break;
                }
                int num = deque();
                inque(num);
            }
        }
    
        sort();
        System.out.print(array[0]+" "+array[1]);
    }
    
    public static int deque() {
        int num = array[0];
        for (int i = 1; i < array.length; i++) {
            array[i - 1] = array[i];
            if (array[i] == 0)
                break;
        }
        return num;
    }
    public static void sort(){
    
        for(int i=0;i<array.length-1;i++){
            for(int j=1;j<array.length;j++){
    
                if(array[i]>array[j]&&array[j]!=0){
                    int temp=array[i];
                    array[i]=array[j];
                    array[j]=temp;
                }
            }
        }
    }
    public static void inque(int num) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == 0) {
                array[i] = num;
                break;
            }
        }
    }
    
    public static boolean check() {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == 0) {
                if (i == 2) {
                    return true;
    
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int testcase = scan.nextInt();
        for (int i = 0; i < testcase; i++) {
            int N = scan.nextInt();
            int K = scan.nextInt();
            function(N,K);
        }
    }

    }


    8년 전
1개의 댓글이 있습니다.
  • 박선준
    박선준

    소팅은 마지막에 어짜피 2개 남으니 상관없다고 해도
    인큐랑 디큐가 너무 느리네요
    앞부터 빈 곳 까지 찾아서 푸시하고
    맨 앞꺼 팝하고 하나씩 땡기는 것보다
    head인덱스랑 tail인덱스 저장해서 인덱스를 옮기는 방법으로 큐를 관리하면 어떨까 싶네용
    O(N^2*K)->O(NK)


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.