백준 2164

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

<문제설명>
카드가 N개 있다. 거기서 첫째 카드를 꺼내면 첫 카드는 버리고 바로 다음 카드는 맨 아래로 넣는다.
ex) 6
1,2,3,4,5,6 -> 1을 버리고 2는 아래 넣고 3,4,5,6,2 ->
3을 버리고 4는 아래, 5,6,2,4 -> 5를 버리고 6을 아래 -> 2,4,6 ->
2를 버리고, 4를 아래로 -> 6,4 -> 6을 버리면 값은 4가 나온다.

<처음 문제 접근>
처음에 배열을 이용해서, for문을 N만큼 돌리고 난뒤, 처음 뽑은 수와 나중에 뽑은 값을 지정 한 후, while문을 돌면서 첫번째 나온 인덱스 값은 버리고, 다음 인덱스는 마지막 인덱스와 같다고 값을 설정해 주어서 풀어보았다.

하지만 이 문제의 의도는 큐를 사용해볼수 있도록 하는 문제였기에 다시 접근해서 풀어봤다.

<문제풀이 1>

public class Main2164 {
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();

    int n[] = new int[2*N -1];
    // 한턴에 한개 사라지고, 뒤에 한개 추가 됨으로 2N-1의 공간이 필요

    for (int i = 1; i <= N; i++) {
        n[i] = i;
    }

    int first_index = 1;
    int last_index = N;

    while (N --> 1){
        first_index ++;
        n[last_index + 1] = n[first_index];
        last_index++;
        first_index++;
    }

    System.out.println(n[first_index]);

}

}

<문제풀이 queue를 사용>

public class Main2164_1 {
	public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    Queue<Integer> queue = new LinkedList<>();
    int N = sc.nextInt();

    for (int i = 0; i <= N; i++) {
        queue.add(i);
    }

    while (queue.size() > 1){
        queue.poll(); // 맨 앞 원소를 버린다.
        queue.add(queue.poll()); // 맨 앞 원소를 버림과 동시에 뒤에 하나를 추가
    }

    System.out.println(queue.poll());
}

}