[BOJ] 2164번 카드2 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        ArrayDeque<Integer> dq = new ArrayDeque<>();

        for (int i = 1; i <= N; i++) {
            dq.addLast(i);
        }

        while (dq.size() > 1) {
            dq.pollFirst();
            dq.addLast(dq.pollFirst());
        }

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

📄 해설

접근

• 문제의 설명에 따라, 단순히 큐의 크기가 1이 될때까지 맨 앞의 원소를 빼서 버리고, 그 다음 맨 앞의 원소를 맨 뒤로 보내는 작업을 반복하면 되는 문제이다.

과정

• 문제 풀이는 간단하다. 1부터 N 까지의 정수를 큐에 넣고, 큐에 정수가 1개 남을때까지 dq.pollFirst() 를 통해 맨 앞의 원소를 빼준다.
• 그 다음 맨 앞의 원소가 된 것은 dq.addLast(dq.pollFirst()) 를 통해 맨 뒤로 옮겨준다.
• 마지막으로 남은 원소를 dq.poll() 를 통해 빼내어 출력한다.

ArrayDeque vs LinkedList ?

• ArrayDeque 가 아니라 LinkedList 를 사용해서 풀어도 된다. 어차피 덱의 기능까지는 사용할 필요가 없다.
• 그런데 ArrayDeque 로 풀이를 올린 이유는 ArrayDeque 와 LinkedList 를 사용했을 때의 메모리 차이에 있다.
  
• 이미지에서 위의 결과가 ArrayDeque, 아래의 결과가 LinkedList 이다.
• 위와 같이 시간에서는 차이가 발생하지 않았지만, 메모리에서 2배에 가까운 효율 차이를 보인다.
• 그 이유는 ArrayDeque 는 LinkedList 와 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용하기 때문이다.
• 그리고 본 문제에서는 특정 원소에 접근할 필요가 없었기 때문에 연산 속도에서의 차이를 보지는 못했는데, ArrayDeque 는 Random Access가 가능하기 때문에 조회에서도 LinkedList 에 비해 빠르다.

• 둘을 비교한 고마운 정리 글이 있어 가져와봤다.
• 그래서 필자는 앞으로 큐를 구현할 때는 ArrayDeque 를 사용하려한다.

위 정리글 이미지 출처 (누르면 이동 됩니당)