[백준 2164-Java ] 카드2 + Queue에 대한 설명

위 문제는 Java의 Queue관련 메서드를 공부한 사람이라면 간단히 풀 수 있는 문제다.

• 내가 먼저 정리해둔 Queue인터페이스의 메서드를 알아보자.
• LinkedList와 ArrayDeque는 Deque 인터페이스의 상속을 받아 양쪽에서 접근이 가능하다.
• 주로 LinkedList를 사용하여 큐를 구현하며 ArrayDeque가 더 효율이 좋은 경우도 있다.
• LinkedList는 LinkedArray처럼 모든 인덱스가 노드(위치)와 밸류(값)을 갖고 있어 중간에 값을 추가하거나 삭제할 때 더 효율적이다.
• ArrayDeque는 순차적인 검색을 할 때 더 효율적이다. 이를 알고 사용하면 더 효율적인 코드를 만들어 낼 수 있을 것이다.

 

 

 

그럼 문제를 살펴보자. 이번 문제는 매우 단순하다. 
https://www.acmicpc.net/problem/2164

2164번: 카드2

 

 

[반복되는 규칙]

숫자의 가장 앞 숫자를 제거 -> 다음 숫자를 가장 뒤로

 

한 번의 반복문으로 수행이 가능하며  N(1 ≤ N ≤ 500,000)의 범위를 갖고있다.

조심해야 할 부분은 반복문의 조건을 설정하는 것이다. que의 사이즈가 1이 남을때까지 수행한다는 조건을 잘 구현해주자.

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static int N;
    public static void main(String[] args) {
        /*
        * 123456
        * 1버리고 2를 뒤로
        * 34562
        * 3버리고 4를 뒤로
        * 5624
        * 5버리고 6을 뒤로
        * 246
        *
        * 2버리고 4를 뒤로
        * 64
        *
        * 6버리고 4를뒤로
        * 4
        *
        *
        * */

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        Deque<Integer> que = new LinkedList();

        for (int i = 1; i <=N; i++) {
            que.add(i);
        }

        while(que.size()!=1){
            int toBack;
            que.pollFirst();
            toBack =  que.pollFirst();
            que.addLast(toBack);
        }

        System.out.println(que.pop());
    }
}