[BOJ][JAVA] 1158 : 요세푸스 문제

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

1158번: 요세푸스 문제

---

오답노트(푸는 동안 사고과정 및 개선점)

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Queue<Integer> q = new LinkedList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            q.offer(i); // 1부터 N까지
        }
        System.out.print("<");
        while(!q.isEmpty()){
            // k-1만큼 뒤로 보내고, poll
            for(int i=0; i<k-1; i++){
                q.offer(q.poll());
            }
            System.out.print(q.poll()+", ");
            if(q.size()==1){
                System.out.print(q.poll());
            }
        }
        System.out.print(">");
    }
}

 

한번에 맞출 수 있었는 데 정말 아쉬운 문제였다. 아이디어는 큐를 사용해서, poll한걸 곧바로 offer해주는, 원형 큐 방식을 사용했다. 95%쯤에서 틀려서 질문게시판의 반례를 계속 캐보다 보니 1 1 일 때 값이 이상하게 나온다는 걸 알게 됐다. 1 1이면 if문으로 선언한 부분만 타게 되어서 <1, >로 출력이 된다. 올바른 답은 <1>이다.

 

---

정답코드

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Queue<Integer> q = new LinkedList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            q.offer(i); // 1부터 N까지
        }
        System.out.print("<");
        while(!q.isEmpty()){
            if(q.size()==1){
                System.out.print(q.poll());
            }else{
                // k-1만큼 뒤로 보내고, poll
                for(int i=0; i<k-1; i++){
                    q.offer(q.poll());
                }
                System.out.print(q.poll()+", ");
            }
        }
        System.out.print(">");
    }
}

 

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^