아니 LinkedList로는 안풀리는데 ArrayDeque로는 풀린다고??
오늘는 쉬면서 알고리즘 문제를 풀고싶어서 간단해보이는 실버 3문제인 풍선 터뜨리기 문제를 풀어보았다.
2346번: 풍선 터뜨리기
1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선
www.acmicpc.net
간단히 요약하자면 위의 문제는 Deque를 사용하면 되는 구현 문제였다. 그래서 Deque를 사용해서 문제를 해결하고자 했고 제출한 코드 다음과 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
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());
int[] next = new int[N];
String[] input = br.readLine().split(" ");
for(int i=0;i<next.length;i++){
next[i] = Integer.parseInt(input[i]);
}
Deque<Integer> balloonQ = new LinkedList<>();
for(int i=0;i<N;i++){
balloonQ.add(i+1);
}
while(!balloonQ.isEmpty()){
Integer balloon = balloonQ.pollFirst();
System.out.print(balloon+" ");
if(balloonQ.size()==0){
break;
}
if(next[balloon-1] < 0){
for(int i=0;i<next[balloon-1]*-1;i++){
balloonQ.addFirst(balloonQ.pollLast());
}
}else{
for(int i=1;i<next[balloon-1];i++){
balloonQ.addLast(balloonQ.pollFirst());
}
}
}
}
}
그런데 계속 메모리 초과가 발생했다ㅠ 하지만 아무리 생각해도 메모리 초과가 발생하는 부분을 찾지 못하였다........... 2시간을 해맨끝에 답지를 보기로 결정하고 수정한 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
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());
int[] next = new int[N];
String[] input = br.readLine().split(" ");
for(int i=0;i<next.length;i++){
next[i] = Integer.parseInt(input[i]);
}
Deque<Integer> balloonQ = new ArrayDeque<>();
for(int i=0;i<N;i++){
balloonQ.add(i+1);
}
while(!balloonQ.isEmpty()){
Integer balloon = balloonQ.pollFirst();
System.out.print(balloon+" ");
if(balloonQ.size()==0){
break;
}
if(next[balloon-1] < 0){
for(int i=0;i<next[balloon-1]*-1;i++){
balloonQ.addFirst(balloonQ.pollLast());
}
}else{
for(int i=1;i<next[balloon-1];i++){
balloonQ.addLast(balloonQ.pollFirst());
}
}
}
}
}
.....혹시 어디가 다른지 찾은 분이 있을까??? 본론으로 빠르게 넘어가기 위해 차이점을 말해주자면 바로 Deque를 선언한 부분이다.
Deque<Integer> balloonQ = new LinkedList<>(); //메모리 초과가 발생한 코드
Deque<Integer> balloonQ = new ArrayDeque<>(); //수정해서 정답을 맞춘 코드
즉 LinkedList로는 발생한 메모리 초과를 ArrayDeque를 이용하면 선언부만 달랐을 뿐인데 메모리 초과를 막을 수 있었다!
어디가 차이가 있길래 메모리 효율이 ArrayDeque가 LinkedList보다 효율이 좋았을까?? 지금부터 알아보도록 하자.
LinkedList와 ArrayDeque의 필드를 살펴보자
우선 LinkedList가 어떻게 구성되었는지 확인해보자. LinkedList의 필드부터 확인해보면 다음과 같다.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
...
}
전형적인 LinkedList의 모습으로 탐색을 위한 시작노드와 끝 노드, 그리고 전체 리스트의 크기를 가지고 있다는 점을 알 수 있다. 그럼 이제 ArrayDeque의 필드를 살펴보자.
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{
/*
* VMs excel at optimizing simple array loops where indices are
* incrementing or decrementing over a valid slice, e.g.
*
* for (int i = start; i < end; i++) ... elements[i]
*
* Because in a circular array, elements are in general stored in
* two disjoint such slices, we help the VM by writing unusual
* nested loops for all traversals over the elements. Having only
* one hot inner loop body instead of two or three eases human
* maintenance and encourages VM loop inlining into the caller.
*/
/**
* The array in which the elements of the deque are stored.
* All array cells not holding deque elements are always null.
* The array always has at least one null slot (at tail).
*/
transient Object[] elements;
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number 0 <= head < elements.length equal to tail if
* the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E));
* elements[tail] is always null.
*/
transient int tail;
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
...
}
주석이 많아서 복잡해 보이지만 필드만 따져보면 구성 요소는 다음과 같다.
- Object[] elements : 값을 저장하는 배열
- head : 가장 처음 노드의 인덱스
- tail : 가장 마지막 노드의 인덱스
- MAX_ARRAY_SIZE : 가능한 객체의 최대 크기
필드만 비교해봐도 LinkedList와 ArrayDeque의 차이점이 드러난다. LinkedList는 전체 원소의 집합을 노드간의 연결로 표현하지만 ArrayDeque는 이름에서 드러나듯 전체 원소의 집합을 배열로 표현했음을 알 수 있다.
이 차이점을 유의하고 한번 추가에 해당되는 addFirst를 확인해보자. LinkedList의 addFirst를 보면 다음과 같다.
public void addFirst(E e) {
linkFirst(e);
}
추가하길 원하는 객체 E를 linkFirst를 이용해서 추가하는 것을 알 수 있다. 이번엔 linkFirst를 확인해보자
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
//맨 처음의 노드 f를 현재 노드 e와 연결
else
f.prev = newNode;
size++;
modCount++;
}
들어오는 객체를 Node라는 객체로 우선 감싸는 것을 알 수 있다. Node가 뭐길래 객체 e를 이용해 다시 생성하는 것 일까??이번엔 Node객체를 한번 살펴보자.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Node 클래스를 보면 다음 노드와 이전 노드, 그리고 현재 노드의 값으로 이루어져 있는 것을 알 수 있다. 즉 객체 1개를 넣기 위해 추가하려는 객체 + 다음 객체 + 이전 객체, 3개의 객체를 생성한다! 즉 다음과 이전 노드의 연결을 위해 메모리를 추가적으로 사용한다는 것이다.
이번에는 ArrayDeque의 addFirst를 알아보자.
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[head = dec(head, es.length)] = e;
if (head == tail)
grow(1);
}
ArrayDeque의 addFirst를 보면 들어오는 객체 e를 기존 ArrayDeque였던 elements에 head(맨 앞 객체의 인덱스)를 이용해 추가하는 것을 알 수 있다. 즉 기존 배열에 인덱스를 이용해 들어오는 객체 e를 그대로 추가한다.
LinkedList와 ArrayDeque의 객체 추가의 원리를 정리하자면 다음과 같다.
(넣으려고 하는 객체) = e
LinkdList => e를 Node로 감싼 뒤 e의 다음 객체와 e의 이전 객체 포인터를 생성
ArrayDeque => e를 인덱스를 이용해 배열에 추가
그러므로 LinkedList는 ArrayDeque보다 메모리를 많이 사용하게 된다!
Deque로 쓰면 ArrayDeque가 LinkedList보다 속도도 빠르다!
ArrayDeque는 구현이 배열로 되어있기 때문에 객체의 구성요소들이 서로 밀접한 메모리 위치에 있다. 하지만 LinkedList는 각각의 요소가 객체로 따로 관리되기 때문에 밀접한 위치에 있지 않을 수 있다. 그래서 가장 맨 앞, 가장 맨 뒤의 값을 꺼내면서 탐색하는 Deque의 특징대로 탐색을 하면 배열 기반의 ArrayDeque가 연결 리스트기반의 LinkedList보다 더 빠르다!
이제 코드로 실험해보자
사용한 코드는 다음과 같다.
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
public class Main {
static int N = 100_000_000;
public static void main(String[] args) throws Exception {
long start = System.currentTimeMillis();
Deque<Integer> deque = new ArrayDeque<>();
// Deque<Integer> deque = new LinkedList<>();
int count = 0;
while(count++ <N){
deque.add(1);
}
while(count++ <N){
deque.addFirst(deque.pollLast());
}
long end = System.currentTimeMillis();
long usedMemory = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
System.out.println("===== ArrayDeque =====");
// System.out.println("===== LinkedList =====");
System.out.println("사용 메모리 : " + (double)usedMemory/1024/1024 + "MB");
System.out.println("걸린 시간 : " + (end - start)+"ms");
}
}
숫자 1을 각 집합에 1억개 넣고 모든 값을 앞에서 부터 꺼내서 탐색하는 간단한 코드이다. ArrayDeque와 LinkedList버전으로 코드를 각각 5번 실행한 결과는 다음과 같다.
ArrayDeque 5회 실행 결과
LinkedList 5회 실행 결과
이를 평균내어 표로 정리하면 다음과 같다.
ArrayDeque)
평균 사용 메모리 = 716mb
평균 걸린 시간 = 2,254ms
LinkedList)
평균 사용 메모리 = 2,323mb
평균 걸린 시간 = 16,954ms
코드 실행 결과 LinkedList가 ArrayDeque보다 메모리는 약 3배, 시간은 약 8배 더 사용된다는 것을 알 수 있다. 그러므로 다음과 같은 결론을 내릴 수 있다.
ArrayDeque가 LinkedList보다 Deque의 구현체로는 더 효율이 좋다!
결론
최종적으로 ArrayDeque가 LinkedList보다 Deque의 구현체로는 더 효율이 좋다는 것을 알게 되었다. 이 글을 읽는 분들이 있다면 꼭 Deque의 구현체로 ArrayDeque를 사용해 알고리즘 문제풀이를 할 때 메모리 초과가 발생하지 않도록 하자
'JAVA' 카테고리의 다른 글
| Integer.valueOf VS Integer.parseInt (0) | 2024.02.13 |
|---|---|
| 최대공약수, 최소공배수를 JAVA로 구해보자(유클리드 호제법, BigInteger) (1) | 2024.02.11 |