JOSEPHUS(조셉푸스) 문제 java 질문드립니다.

  • pjy1368
    pjy1368

    Queue 방식으로 다음과 같이 풀었을 때, 시간초과가 납니다.
    시간을 어떻게 줄일 수 있을까요?

    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    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 Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
    
        int C = Integer.parseInt(br.readLine());
    
        while (C-- > 0) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
    
            Queue<Integer> q = new LinkedList<>();
            for (int i = 0; i < N; i++) {
                q.offer(i + 1);
            }
    
            while (q.size() > 2) {
                q.poll();
                for (int i = 0; i < K - 1; i++) {
                    int n = q.poll();
                    q.offer(n);
                }
            }
    
            bw.write((q.poll()) + " " + (q.poll()) + "\n");
        }
    
        bw.flush();
        bw.close();
        br.close();
    }

    }


    4년 전
1개의 댓글이 있습니다.
  • BueVonHon
    BueVonHon

    정말 문제가 있어 보이네요
    입출력에서는 최대한 빠르게 할만큼 한 것 같은데...


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