(JAVA) [BOJ]백준 1158번, 요세푸스 문제

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

1158번: 요세푸스 문제

1158, 요세푸스 문제

[ 난이도 : 실버 4 ]

이번 문제는 큐를 사용해서 풀어보겠다.

# Process

input

: N 과 M 을 입력받고, N만큼의 수를 큐에 넣어준다.

static int N, M;
static Queue<Integer> Q = new LinkedList<>();

static void input() 
{
    N = scan.nextInt(); M = scan.nextInt();
    for(int i=1; i<=N; i++) Q.offer(i);
}

 

순회

: M 번째 수를 출력해야 하기 때문에 M-1 번째까지의 수를 poll 로 뽑고 그대로 뒤에 넣어준다.

M-1 번째까지 수를 모두 출력하면 그 다음 수는 M번째 수이기 때문에 그 수를 출력하는 것을

큐의 사이즈가 1이 될때까지 반복한다.

1이 남은 수를 최종적으로 출력해주면 해결할 수 있는 문제이다.

sb.append("<");

while(Q.size() != 1)
{
    for(int i=0; i<M-1; i++) Q.offer(Q.poll());

    sb.append(Q.poll()+", ");
}

sb.append(Q.poll()+">");

System.out.println(sb.toString());

 

전체 코드

static int N, M;
static Queue<Integer> Q = new LinkedList<>();

static void input() 
{
    N = scan.nextInt(); M = scan.nextInt();
    for(int i=1; i<=N; i++) Q.offer(i);
}

static void pro()
{  
    sb.append("<");

    while(Q.size() != 1)
    {
        for(int i=0; i<M-1; i++) Q.offer(Q.poll());

        sb.append(Q.poll()+", ");
    }

    sb.append(Q.poll()+">");

    System.out.println(sb.toString());
}

public static void main(String[] args) 
{
    input();
    pro();
}