백준 1158번 (요세프스 문제)

백준 1158번 문제는 아래와 같다.

이 문제를 풀어보자면 리스트 형태로 했을때 list1[2] 즉, 3번째 자리에 있는것을 뽑아서 출력시켜서 다른 다른 list2 에 넣은후 출력하라는 말이다. 

 

여기까지 생각해봤을때 결국 list1 에 있던 3번째 자리마다 list2에 넣는 순간 삭제하고 삭제한 상태의 list1에서 3번째 자리를 뽑고 삭제하는것을 반복해야한다. 그러한 방식을 생각해봤을때 JAVA에서 적당한 클래스는 큐(Queue)이다.

 

 

그렇다면 큐(Queue)란 무엇일까?

Queue의 사전적 의미는 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미한다. 큐클레스는 줄을 지어 순서대로 처리되는것이다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가진다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말한다. 

 

 

Queue의 특징은?

1. FIFO(First In First Out)로서 먼저 들어간 자료가 먼저나오는 자료 구조

2. 큐는 한쪽 끝은 front로 정하여 삭제 연산만 수행하고 다른 한쪽은 rear로 정하여 삽입 연산만 수행함

3. 그래프의 넓이 우선 탐색(BFS)에서 사용 -> ???

5. 컴퓨터 버퍼에서 주로 사용, 마구 입력되었으나 처리를 하지 못할때, 버퍼(큐)를 만들어 대기 시킴 -> ???

 

Queue의 선언하는 방법은?

import java.util.LinkedList;
import java.util.Queue;
//int 형 queue선언, LinkedList 이용
Queue<Integer> queue = new LinkedList<>(); 
//String형 queue 선언, LinkedList 이용
Queue<String> queue = new LinkedList<>();

 

 

Queue의 메소드

Queue<Integer> queue = new LinkedList<>();
queue.offer(0); //queue에 값 0 추가
queue.poll(); //queue에 첫번째 값을 반환하고 제거
queue.remove(); //queue에 첫번째 값을 제거
queue.clear(); //queue 초기화, 아예 다 삭제시킴

 

 

이제 다시 문제로 돌아오면 N = 4이고 K = 2라고 하면 

q = {1, 2, 3, 4}

q = {2, 3, 4, 1} => 2를 list에 넣고 삭제 (poll()이용)

 

q = {3, 4, 1}

q = {4, 1, 3} => 4를 list 넣고 삭제 

 

q = {1, 3}

q = {3, 1} => 3을 list에 넣고 삭제

 

q={1} 

=> 1을 list에 넣고 삭제 

 

이런식으로 가야한다. 그러면 add로 q라는것에 N만큼 넣은 후에 poll()과 add()를 이용한다. 

즉, poll은 반환하고 난 후 삭제니까 그것을 add메소드와 합쳐서 q.add(q.poll())을 이용해서 하면 

 

하지만, 여기서 주의사항이 있다. 문제의 출력을 보면 밑에와 같다.

 

 

출력했을때 "<", ">", ","이 포함되어있다.  따라서 앞에서 저런것들을 넣어주기위해 list형태가 아닌 String형태로 바꿔서 메소드 append를 이용해서 넣어준다. 근데 여기서 또 조심해야하는것이 하나 있는데 그건 바로 끝에도 ","가 아닌 ">"를 붙여야한다. 따라서 끝에 전까지 append를 이용해 ","를 넣고 마지막 원소후에는 ">"를 넣어야한다는 점이다. 

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;
import java.util.List;

public class Main{

	public static void main(String[] args){
    
    	Scanner sc = new Scanner(System.in);
        Queue<Integer> q = new LinkedList<>();
        StringBuilder s = new StringBuilder();
        s.append('<');
        
        int N = sc.nextInt();
        int K = sc.nextInt();
 		
        for(int i = 1; i <= N; i++){
        	q.add(i);
        }
        
        while(q.size() > 1){
        	for(int i = 1; i < K; i++){
            	q.add(q.poll());
            }
            s.append(q.poll()).append(", ");
        }
        s.append(q.poll()).append(">");
        System.out.println(s);
 	}
}

이런식으로 코드가 나온다.