[백준] 2164번 카드2 with ArrayList vs LinkedList vs ArrayDeque 성능 비교

조은경·2025년 2월 14일
Java백준
2

1. 문제

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

N장의 카드가 1부터 N까지 순서대로 쌓여 있을 때, 다음 두 가지 동작을 반복하여 마지막 한 장이 남을 때까지 진행한다.

  1. 제일 위에 있는 카드를 버린다.
  2. 그다음 제일 위에 있는 카드를 제일 아래로 옮긴다.

이 과정을 반복한 후, 마지막에 남는 카드를 출력하는 문제이다.

2. 풀이

1차 시도

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>();
        for (int i=1; i<=n; i++) {
            list.add(i);
        }
        while (list.size() > 1) {
            list.remove(0);
            if (list.size() == 1)
                break;
            list.add(list.remove(0));
        }
        System.out.println(list.get(0));
    }
}

ArrayList를 사용하여 가장 위에 있는 카드를 삭제하고, 그 다음 카드를 마지막 위치로 이동하는 과정을 처리하였다. => 시간 초과가 발생했다.

2차 시도

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> q = new ArrayDeque<>();
        for (int i=1; i<=n; i++) {
            q.add(i);
        }
        while (q.size() > 1) {
            q.poll();
            if (q.size() == 1)
                break;
            q.add(q.poll());
        }
        System.out.println(q.poll());
    }
}

ArrayList 대신 ArrayDeque를 사용하여 가장 위에 있는 카드를 삭제하고, 그 다음 카드를 마지막 위치로 이동하는 과정을 처리하였다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> list = new LinkedList<>();
        for (int i=1; i<=n; i++) {
            list.add(i);
        }
        while (list.size() > 1) {
            list.remove(0);
            if (list.size() == 1)
                break;
            list.add(list.remove(0));
        }
        System.out.println(list.get(0));
    }
}

ArrayList 대신 LinkedList를 사용한 경우 역시 시간 초과 문제가 발생하지 않았다.

✏️ ArrayList와 ArrayDeque 성능 비교

연산ArrayListArrayDeque
컬렉션 구성동적 배열원형 배열
데이터 접근O(1) (배열처럼 인덱스를 통한 임의 접근)O(N) (배열 탐색 필요)
앞에서 삽입O(N) (모든 요소를 한 칸씩 이동)O(1)
뒤에서 삽입O(1) / O(N)O(1)
앞에서 삭제O(N) (모든 요소를 한 칸씩 이동)O(1)
뒤에서 삭제O(1)O(1)
중간 삽입 / 삭제O(N)O(N)
검색O(N) (배열 순차 탐색)O(N) (배열 순차 탐색)

자바에서 ArrayList와 ArrayDeque는 모두 배열을 기반으로 하는 자료구조이다. 하지만 사용 목적과 성능 차이가 있기 때문에 상황에 따라 적절한 자료구조를 선택해야 한다.

1️⃣ ArrayList

  • ArrayList는 기본적으로 일정 크기의 배열을 생성하고, 데이터가 추가되면 배열의 크기를 늘려가면서 저장하는 방식으로 동작한다.

  • 데이터 추가는 위치에 따라 성능 차이가 발생한다.

    • 앞이나 중간에서 추가할 경우 추가된 위치 이후의 모든 요소를 한 칸씩 뒤로 이동해야 하므로 O(N)의 시간이 걸린다.
    • 뒤에서 추가하는 경우는 단순히 마지막 위치에 삽입하면 되므로 평균 O(1)의 시간에 수행된다.

  • 하지만, 배열의 크기가 가득 찬 경우 새로운 배열을 생성하고 기존 데이터를 복사해야 하므로 O(N)의 시간이 소요될 수도 있다.

  • 데이터 접근은 배열처럼 O(1) 시간에 가능하여 빠르지만, 데이터 삭제는 삭제한 인덱스 이후의 모든 요소를 한 칸씩 이동해야 하므로 O(N) 시간이 소요된다.

2️⃣ ArrayDeque

  • ArrayDeque는 원형 배열을 기반으로 하여 배열의 끝이 배열의 처음으로 이어지는 구조를 갖는 자료구조이다.

  • 데이터 추가는 앞과 뒤에서 모두 O(1)의 시간에 수행된다. 기존 요소를 이동하지 않고 배열의 시작과 끝을 가리키는 인덱스를 조정하는 방식으로 동작하기 때문이다.

  • 데이터 접근은 특정 인덱스를 직접 조회할 수 없으며, 배열을 순차적으로 탐색해야 하므로 O(N)의 시간이 걸린다.

  • 데이터 삭제는 앞과 뒤에서 모두 O(1)에 수행되며, 기존 요소를 이동할 필요가 없어 빠르게 처리된다.

✏️ ArrayList와 LinkedList 성능 비교

연산ArrayListArrayDeque
컬렉션 구성동적 배열이중 연결 리스트
데이터 접근O(1) (배열처럼 인덱스를 통한 임의 접근)O(N) (앞에서부터 순차 접근 필요)
앞에서 삽입O(N) (모든 요소를 한 칸씩 이동)O(1) (포인터 변경)
뒤에서 삽입O(1) / O(N)O(1) (참조 변경)
앞에서 삭제O(N) (모든 요소를 한 칸씩 이동)O(1) (포인터 변경)
뒤에서 삭제O(1)O(1)
중간 삽입 / 삭제O(N)O(N) (이동 후 포인터 변경)
검색O(N) (배열 순차 탐색)O(N) (노드를 순차적으로 탐색)

자바에서 ArrayList와 LinkedList는 모두 List 인터페이스를 구현한 자료구조이지만, 내부 구현 방식이 다르므로 사용 목적과 성능 차이가 발생한다.

1️⃣ LinkedList

  • LinkedList는 이중 연결 리스트로 구현되어 있으며, 각 노드가 이전 노드와 다음 노드를 가리키는 방식으로 구성된다.

  • 데이터 추가는 위치에 따라 성능 차이가 발생한다.

    • 앞이나 뒤에서 추가할 경우 단순히 새로운 노드를 연결하면 되므로 O(1)의 시간에 수행된다.
    • 중간에서 추가할 경우는 추가할 위치를 찾기 위해 O(N)의 탐색이 필요하며, 이후 O(1)의 포인터 조정이 이루어진다.

  • 데이터 접근은 특정 인덱스를 바로 조회할 수 없으며, 첫 번째 노드부터 순차 탐색해야 하므로 O(N)의 시간이 걸린다.

  • 데이터 삭제는 위치에 따라 성능 차이가 발생한다.

    • 앞이나 뒤에서 삭제할 경우 포인터 변경만 하면 되므로 O(1)의 시간이 걸린다.
    • 중간에서 삭제할 경우는 삭제할 위치를 찾기 위해 O(N)의 탐색이 필요하며, 이후 O(1)의 포인터 조정이 이루어진다.

✅ 결론

✔️ ArrayList는 데이터 접근이 빠르지만, 삽입/삭제 시 삽입 또는 삭제한 위치 이후의 배열 요소를 한 칸씩 이동시켜야 하므로 성능이 저하된다.
✔️ ArrayDeque는 배열의 요소를 이동할 필요가 없어, 삽입/삭제가 빠르다.
✔️ LinkedList는 데이터 접근이 느리지만 참조 변경을 통해 빠른 삽입/삭제가 가능하다.

3. 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> q = new ArrayDeque<>();
        for (int i=1; i<=n; i++) {
            q.add(i);
        }
        while (q.size() > 1) {
            q.poll();
            if (q.size() == 1)
                break;
            q.add(q.poll());
        }
        System.out.println(q.poll());
    }
}
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> list = new LinkedList<>();
        for (int i=1; i<=n; i++) {
            list.add(i);
        }
        while (list.size() > 1) {
            list.remove(0);
            if (list.size() == 1)
                break;
            list.add(list.remove(0));
        }
        System.out.println(list.get(0));
    }
}
profile
조은경
이전 포스트

[백준] 2170번 선 긋기

다음 포스트

[백준] 20920번 영단어 암기는 괴로워

0개의 댓글