[백준] 카드2

2164번: 카드2

 

풀이 1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

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());
		Queue<Integer> q = new ArrayDeque<>();
		for (int i = 1; i <= n; i++) {
			q.offer(i);
		}
		while (q.size() != 1) {
			q.poll();
			q.offer(q.poll());
		}
		System.out.println(q.peek());
	}

}

 

풀이 2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

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());
		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= n; i++) {
			q.offer(i);
		}
		while (q.size() != 1) {
			q.poll();
			q.offer(q.poll());
		}
		System.out.println(q.peek());
	}

}

 

풀이 비교

ArrayDeque가 LinkedList에 비해 더 빠르고 메모리 사용량이 적게 나타났습니다. 아래는 이러한 차이를 설명하는 몇 가지 이유입니다:

내부 배열 구조: ArrayDeque는 내부적으로 동적으로 크기가 조절되는 배열을 사용합니다. 이로 인해 요소에 대한 빠른 접근과 작업이 가능하며, 배열의 구조가 메모리를 효율적으로 활용할 수 있습니다. 큐의 요소를 뽑아내고 다시 아래로 옮기는 작업은 배열에서 인덱스 조작만으로 이루어지므로 ArrayDeque에서는 이러한 작업이 빠릅니다.

메모리 할당 및 해제 오버헤드: ArrayDeque는 초기에 고정 크기 배열을 할당하고, 큐의 크기가 증가할 때 필요한 크기만큼만 배열을 재할당하여 메모리 사용량을 최적화합니다. 반면에 LinkedList는 요소를 추가할 때마다 새로운 노드를 동적으로 할당하고, 더블 링크드 리스트의 특성상 메모리 할당 및 해제 오버헤드가 더 큽니다.

이 문제에서는 큐에서 요소를 뽑아내고 다시 아래로 옮기는 작업이 빈번하게 발생하므로 ArrayDeque가 이러한 작업을 더 효율적으로 처리할 수 있습니다. LinkedList의 경우 요소를 노드로 저장하고, 노드 간의 링크를 조작해야 하므로 추가적인 오버헤드가 발생할 수 있습니다.

 

참고

ArrayDeque는 내부적으로 원형 배열을 사용하며, 큐의 요소를 추가 및 삭제할 때 배열 내의 요소들을 이동시키는 작업 없이 큐의 동작을 구현합니다. 이로 인해 ArrayDeque는 큐의 요소를 추가하거나 삭제할 때 데이터의 순서를 유지하려는 작업에서 추가적인 오버헤드가 발생하지 않습니다.