[백준] 1158번 요세푸스 문제 JAVA (자바) 풀이

문제 1158번

 : 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고 이제 순서대로 K번째 사람을 제거한다. 
 : 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
 : 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
 : 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

 

 

 [입력]

 : 첫째 줄에 N K 입력

 

 

 [출력]

 : 예제와 같이 요세푸스 순열을 출력한다.

 

 [큐 연산]

 

init()	큐 초기화
create()	큐 생성
isEmpty()	큐 비어있는지 검사
isFull()	큐 가득 찼는지 검사
enqueue(e)	큐 맨 뒤에 e 추가
dequeue()	큐 맨 앞의 값 삭제
peek()	큐 맨 앞의 값 출력 (큐가 비어있는 경우 null 반환)
element()	큐 맨 앞의 값 출력 (큐가 비어 있는 경우 에러 발생)
offer(e)	큐의 맨 뒤에 e 추가 (큐가 비어있는 경우 null 반환)
add(e)	큐의 맨 뒤에 e 추가(큐가 비어 있는 경우 에러 발생)
poll()	큐의 맨 앞의 값 제거하고 출력 (큐가 비어있는 경우 null 반환)
remove()	큐의 맨 앞의 값 제거하고 출력 (큐가 비어 있는 경우 에러 발생)

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); 
        int K = Integer.parseInt(st.nextToken());
        Queue<Integer> que = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        
        for(int j=1; j<=N ;j++){
            que.offer(j);
        }
        
        sb.append("<");
        
        while(que.size()!=1){
            for(int i = 0; i<K-1; i++){
                que.offer(que.poll()); 
            }
                sb.append(que.poll()+", ");  
        }
        sb.append(que.poll() + ">"); 
        bw.write(sb.toString());
        bw.flush();
    }
}

 

 [해설]

 :  StringTokenizer st = new StringTokenizer(br.readLine()); 문자열 하나하나 토큰으로 구분

 :  int N = Integer.parseInt(st.nextToken());  입력 1

 :  int K = Integer.parseInt(st.nextToken());  입력 2

 :  Queue<Integer> que = new LinkedList<>();  큐 선언

 :  StringBuilder sb = new StringBuilder();  각각 이어서 붙여줄거라 누적되어 출력할 수 있도록 설정

 :  for(int j=1; j<=N ;j++){  1부터 순서대로 넣으려고 while(n-->0)은 사용하지 않았다
             que.offer(j);  일단 1~n까지 큐에 넣는다
        }

 :  sb.append("<");  < 부터 먼저 출력하기

 :  while(que.size()!=1){  숫자랑 ,랑 같이 출력할건데 마지막 숫자는 ,빼고 출력해야해서 하나 남을때까지만 출력
            for(int i = 0; i<K-1; i++){  k번째 숫자 앞에 있던 숫자들은 다시 뒤로 가서 줄 서야해서 k-1로 설정
                que.offer(que.poll());  뺀 애들 다시 뒤에넣기                            
            }
                   sb.append(que.poll()+", ");  k 앞에 있는 것들을 뒤로 몰았으니 k가 맨앞에 있다 ( k 빼기 )
      }
 
 :  sb.append(que.poll() + ">");  마지막 1개 빼주고 > 까지 출력하기

 :  bw.write(sb.toString()); toString은 객체를 문자열로 변환하는 메소드
  

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

 

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

1158번: 요세푸스 문제

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *