[백준/Java] #2346 풍선 터뜨리기 - 메모리 초과 해결 (feat. LinkedList vs ArrayDeque)

 

 

문제

 

 

 

 

코드

 

처음에 `Deque`을 `LinkedList`로 구현했다가 메모리 초과 문제가 발생했고,

`ArrayDeque`으로 바꾸니 바로 풀 수 있었다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

int N = Integer.parseInt(br.readLine());
Deque<Integer> d = new ArrayDeque<>();
int[] arr = new int[N];

StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
    arr[i] = Integer.parseInt(st.nextToken());
    d.offer(i + 1);
}

sb.append("1 ");
int poll = d.poll();
int move = arr[0];

while (!d.isEmpty()) {
    if (move > 0) {
        for (int i = 1; i < move; i++) {
            d.offer(d.poll());
        }
        poll = d.poll();
    } else if (move < 0) {
        for (int i = 1; i < -move; i++) {
            d.offerFirst(d.pollLast());
        }
        poll = d.pollLast();
    }
    move = arr[poll - 1];
    sb.append(poll).append(" ");
}
System.out.println(sb);

 

풍선이 가지고 있는 숫자가 양수인 경우 해당 숫자가 나올 때까지 맨 앞의 요소를 꺼내 덱의 맨 뒤로 넣고,

음수인 경우는 반대로 맨 뒤의 요소를 덱의 맨 앞에 넣었다.

 

 

 

 

알고리즘은 모두 동일한데 `ArrayDeque`을 사용하니 해결이 되어서, 두 클래스의 차이를 알아보았다.

 

 

 

LinkedList vs ArrayDeque

 

공식 문서와 몇몇 기술 블로그에 정리된 글을 참고하여 차이점을 정리해 보겠다.

 

`LinkedList`와 `ArrayDeque`은 둘 다 `Deque`을 구현한 클래스로, 양쪽 끝에서 요소 추가 또는 제거가 가능하다.

 

 

 

LinkedList

 

• 이중 연결 리스트로 구현되어 있음
• 요소의 null값을 허용함
• 각 요소는 자신의 이전 요소와 다음 요소에 대한 참조를 가짐
• 중간에 있는 요소에 대한 접근이 빠름
• 각 요소의 삽입 및 제거는 해당 요소에 대한 참조를 찾는 작업이 필요함

 

 

 

 

ArrayDeque

 

• 내부적으로 배열로 구현되어 있음
• 요소의 null값을 허용하지 않음
• 용량 제한이 없고 필요에 따라 크기가 자동으로 조절됨
• 요소의 삽입 및 제거는 배열의 처음과 끝에서만 발생함
• stack으로 사용될 때 Stack보다 빠르고, queue로 사용될 때 LinkedList보다 빠름

 

 

공식 문서의 ArrayDeque에 밑줄 친 부분이 이번 문제를 푸는 핵심이었다.

 

이번 문제의 경우 1. Queue로 사용했고, 2. 중간 요소를 찾지 않고 덱의 처음과 끝에서의 요소의 변경(추가/삭제)이 일어났기 때문에

ArrayDeque을 사용하는 것이 정답이었던 것 같다.