[BOJ] 백준 1158번 요세푸스 문제 자바(java) 풀이(큐, 리스트)

BOJ 1158번 요세푸스 문제1 자바(java) 풀이

• 랭크 : 실버5
• 풀이시간: 5분
• 백준 1158번 요세푸스 문제1
  
  
  

문제 정리

1. 1~N번까지 N명의 사람이 원 모양으로 앉아있다.
2. k가 주어질때 k번째 사람을 제거한다.
3. 한 사람이 제거되면 남은 사람들로 이루어진 원에서 2번을 반복한다.
4. N명의 사람이 모두 제거될 때까지 계속된다.
5. 사람들이 제거 되는 순서를 출력해라.
   
   
   

문제 풀이

이 문제는 요세푸스 문제0번과 똑같이 제출해도 통과할 수 있습니다.
즉 naive하게 문제에서 주어진대로 구현하면 통과할 수 있습니다.
하지만 이 문제는 queue를 이용하여 작성해보았습니다.
queue에서 뺄 필요 없이 ArrayList를 이용하면 뺏다 넣었다 하지 않기 때문에 더 빠르게 가능합니다.

1. 1~N까지 queue에 모두 넣습니다.
2. k-1번째 까지 숫자를 빼서 뒤에 차례로 넣습니다.
3. k번째 사람을 제거하고 출력합니다.
4. 2,3번을 queue에 1개가 남을때까지 반복합니다.
5. 마지막 element를 출력형식에 맞게 출력합니다.
   
   
   

문제 풀이

1. naive한 풀이

• 실행시간: 2024ms
• 메모리: 22020 KB

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

class Main {
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());
boolean[] visited = new boolean[n+1];

    int idx = k;
    int flag = n;
    System.out.print("<");
    while(flag > 1){
        int cnt = 0;    // 몇 번째 사람인지
        System.out.print(idx + ", ");

        // 사람 제거
        visited[idx] = true;

        // 남은 사람수
        flag--;
        while(true){
            // 원으로 되어있으므로 n을 넘어가는 경우 처리해준다.
            // 0인 경우는 index는 1부터 시작이므로 1로 해준다.
            idx = ((idx+1) % (n+1)) == 0 ? 1 : (idx+1) % (n+1);

            // 죽지 않은 사람 체크
            if(!visited[idx])
                cnt++;
            // k번째 사람을 찾은 경우
            if(cnt == k)
                break;
        }
    }

    System.out.println(idx + ">");        
}

}

<br><br>

2. <span style="color:blue; font-size:13pt">queue이용한 풀이</span>
- 실행시간: 524ms
- 메모리: 278312 KB
```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.LinkedList;

class Main {
    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());
        Queue<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        sb.append("<");

        // q에 N명의 사람 넣기
        for(int i=1; i<=n; i++)
            q.offer(i);

        while(q.size() > 1){
            // k-1번 째 사람까지 queue에서 빼서 넣기
            for(int i=0; i<k-1; i++)
                q.offer(q.poll());

            sb.append(q.poll() + ", ");    // k번째 사람 제거
        }
        sb.append(q.poll() + ">");
        System.out.println(sb);
    }
}