[자료구조] 백준 2346 풍선 터뜨리기

2346번: 풍선 터뜨리기

https://www.acmicpc.net/problem/2346

 

# 메모리 초과 판정을 받은 코드 (LinkedList 사용)

import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입출력을 위한 BufferedReader 와 BufferedWriter
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 풍선의 수 N
        long n = Long.parseLong(br.readLine());

        // 1~N 번 풍선을 담을 LinkedList
        LinkedList<Long> ballon_list = new LinkedList<>();
        for (long i = 0; i < n; i++) {
            ballon_list.addLast(i + 1);
        }

        // 문자열 분리를 위한 StringTokenizer
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 1~N 번 풍선의 종이 값을 담을 LinkedList
        LinkedList<Long> paper_list = new LinkedList<>();
        for (long i = 0; i < n; i++) {
            paper_list.addLast(Long.parseLong(st.nextToken()));
        }

        // 다음에 터뜨릴 풍선
        long next = 0;

        for (long i = 0; i < n; i++) {
            if (i == 0) {
                // 처음에는 1번 풍선 터뜨리기
                bw.write(String.valueOf(ballon_list.removeFirst()) + " ");
                next = paper_list.removeFirst();
            } else {
                // 이후에는 next 값에 따라 풍선 터뜨리기
                // next가 양수라면 오른쪽으로 돌리고, 음수라면 왼쪽으로 돌림
                if (next > 0) {
                    for (long k = 1; k < next; k++) {
                        ballon_list.addLast(ballon_list.removeFirst());
                        paper_list.addLast(paper_list.removeFirst());
                    }
                    bw.write(String.valueOf(ballon_list.removeFirst()) + " ");
                    next = paper_list.removeFirst();
                } else {
                    for (long k = 1; k < -next; k++) {
                        ballon_list.addFirst(ballon_list.removeLast());
                        paper_list.addFirst(paper_list.removeLast());
                    }
                    bw.write(String.valueOf(ballon_list.removeLast()) + " ");
                    next = paper_list.removeLast();
                }
            }
        }

        // Reader 버퍼 닫기
        br.close();

        // Writer 버퍼 비운 뒤 닫기
        bw.flush();
        bw.close();
    }
}

• 처음에는 요세푸스 문제 때와 같이 LinkedList를 사용해 코드를 작성했다.
• 그러나 메모리 초과 판정을 받았고 자료구조를 ArrayDeque로 변경하고 나서 정답 처리를 받을 수 있었다.

 

# 코드 (ArrayDeque 사용)

import java.io.*;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입출력을 위한 BufferedReader 와 BufferedWriter
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 풍선의 수 N
        long n = Long.parseLong(br.readLine());

        // 1~N 번 풍선을 담을 ArrayDeque
        ArrayDeque<Long> ballon_dq = new ArrayDeque<>();
        for (long i = 0; i < n; i++) {
            ballon_dq.offerLast(i + 1);
        }

        // 문자열 분리를 위한 StringTokenizer
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 1~N 번 풍선의 종이 값을 담을 ArrayDeque
        ArrayDeque<Long> paper_dq = new ArrayDeque<>();
        for (long i = 0; i < n; i++) {
            paper_dq.offerLast(Long.parseLong(st.nextToken()));
        }

        // 다음에 터뜨릴 풍선
        long next = 0;

        for (long i = 0; i < n; i++) {
            if (i == 0) {
                // 처음에는 1번 풍선 터뜨리기
                bw.write(String.valueOf(ballon_dq.pollFirst()) + " ");
                next = paper_dq.pollFirst();
            } else {
                // 이후에는 next 값에 따라 풍선 터뜨리기
                // next가 양수라면 오른쪽으로 돌리고, 음수라면 왼쪽으로 돌림
                if (next > 0) {
                    for (long k = 1; k < next; k++) {
                        ballon_dq.offerLast(ballon_dq.pollFirst());
                        paper_dq.offerLast(paper_dq.pollFirst());
                    }
                    bw.write(String.valueOf(ballon_dq.pollFirst()) + " ");
                    next = paper_dq.pollFirst();
                } else {
                    for (long k = 1; k < -next; k++) {
                        ballon_dq.offerFirst(ballon_dq.pollLast());
                        paper_dq.offerFirst(paper_dq.pollLast());
                    }
                    bw.write(String.valueOf(ballon_dq.pollLast()) + " ");
                    next = paper_dq.pollLast();
                }
            }
        }

        // Reader 버퍼 닫기
        br.close();

        // Writer 버퍼 비운 뒤 닫기
        bw.flush();
        bw.close();
    }
}

• 바로 직전 '덱' 문제풀이에서도 다루었지만, ArrayDeque 는 deque의 양 끝에서 삽입/삭제 연산이 일어날 경우 시간 복잡도가 O(1)이므로 삽입/삭제 성능이 우수하다.
• 또한 Random access가 가능하기에 원소 조회 시에도 속도가 빠르다.
• LinkedList도 삽입/삭제 연산 성능이 좋은 편이지만, 특정 원소 접근 시의 성능은 ArrayDeque에 비해 떨어진다.
• ArrayDeque는 LinkedList 에 비해 cache-locality에 더 친숙하여 연산 속도가 빠르다고 한다.

메모리의 측면에서도 ArrayDeque은 LinkedList와 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용한다.

 

이러한 차이점 때문에 원소를 계속 돌려야 하는 큐 구현 시 ArrayDeque가 LinkedList보다 속도와 메모리 측면에서 더 효율적이라고 할 수 있으며, 이는 자바 공식문서에도 언급되어 있다고 한다.

 

"This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue."