[코딩테스트] Java 정리 - 2 (1)

코딩테스트에서 자주 사용되는 Java 자료구조 등을 정리했습니다.
컬렉션 프레임워크는 다양한 자료구조를 직접 구현하지 않고, 쉽게 사용할 수 있도록 제공해줍니다.

A. 기초

1. 배열 (Array)

동일한 타입의 데이터를 연속적으로 저장하는 고정된 크기의 자료구조입니다.
새로운 데이터 삽입/삭제는 불가능하고, 값을 변경하는 것은 가능합니다.
인덱스를 이용해 요소에 접근 및 변경하는 것의 시간 복잡도는 O(1)입니다.
연속된 메모리의 공간으로 메모리 관리가 효율적입니다.

• 선언 및 초기화 :
  • int[] arr = new int[N];
  • int[] arr = {1, 2, 3};
• 다차원 배열 : int[][] matrix = new int[N][M];
• java.util.Arrays 클래스 : 배열 관련 유용한 메서드 제공
  • Arrays.sort(arr) : 배열 정렬 - (O(NlogN) : Dual-Pivot QuickSort / Tim-Sort)
  • Arrays.copyOf(arr, 복사할 길이) : 배열 복사
  • Arrays.copyOfRange(arr, 0, position) : 부분 배열 반환
  • Arrays.fill(arr, value) : 배열의 모든 요소를 특정 값으로 채우기 (int라면 기본 0)
  • Arrays.toString(arr) : 배열 모든 요소 출력
  • arr.length : 배열의 길이 출력
  • arr.clone() : 배열 복사
  • Arrays.asList(arr) : 배열을 리스트로 변환

B. List 인터페이스

순서 O / 중복 O

2. ArrayList 클래스

가변 크기의 배열이므로, 값을 삽입 혹은 삭제를 할 수 있습니다.
맨 뒤에 삽입하거나 삭제할 때는 평균 시간 복잡도가 O(1)이지만, 중간에 삭제나 삽입할 때는 O(N)까지 커질 수 있습니다.
인덱스를 통한 접근이 빠릅니다. (내부적으로 배열 기반)

선택 시 고려사항

• 임의 접근이라는 특징이 있어 인덱스로 바로 접근할 수 있으므로 데이터에 빈번하게 접근하는 경우 효율적
  • ex. 그래프를 표현할 때 간선 여부도 시간 복잡도 O(1)로 판단할 수 있습니다.
• 하지만 메모리 공간을 충분히 확보해야 함

1. 할당할 수 있는 메모리 크기 확인 : 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있습니다.
   • OS마다 다르지만 보통 정수형 1차원 배열은 1000만 개, 2차원 배열은 3000 * 3000 크기를 최대로 생각
2. 중간 데이터 삽입이 많은지 확인 : 선형 자료구조이므로 중간/처음에 빈번하게 삽입하면 시간 복잡도가 높아져 시간 초과가 발생할 수 있습니다.

기본 사용 예시

import java.util.ArrayList;

public class ListExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();  // 인터페이스로 선언
        ArrayList<Integer> list = new ArrayList<>();  // 클래스로 선언
        list.add(10);  // 요소 추가
        list.add(20);
        list.add(30);
        list.add(idx, 40);  // 원하는 위치에 추가

        System.out.println(list.get(2));  // 인덱스로 값에 접근 (30)
        list.set(1, 100);  // 해당 인덱스의 값 변경
        list.remove(list.size() - 1);  // 마지막 요소 삭제 (원하는 인덱스 데이터 삭제)
        list.remove(Integer.valueOf(100));  // 값이 100인 요소 삭제 (오버로딩 주의)
        System.out.println(list);  // [10]

        for (int num : list) {  // for-each문
            System.out.println(num);
        }
    }
}

연관 메서드

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 4, 5, 3));
System.out.println(list.size());  // 5
System.out.println(list.isEmpty());  // false
Collections.sort(list);  // 오름차순 정렬 [1, 2, 3, 4, 5]
Collections.sort(list, Collections.reverseOrder());  // 내림차순 정렬
list.contains(3);  // 해당 값이 있는지 출력 true
list.indexOf(3);  // 해당 값의 인덱스 반환
list.addAll(list2);  // list 뒤에 list2가 삽입
Collections.addAll(list, arr);  // 배열을 리스트로 변환
Integer[] arr = list.toArray(new Integer[list.size()]);  // 리스트를 배열로 변환 (원시형X, for문이 더 빠름)
List<Integer> list3 = list.subList(1, 3);  // 특정 범위의 데이터 List로 반환

2차원 ArrayList

ArrayList<ArrayList<Integer>> matrix = new ArrayList<>();

// 초기화 예시 (행 추가)
for (int i = 0; i < 3; i++) {
    matrix.add(new ArrayList<>());
}

// 값 추가
matrix.get(0).add(1);
matrix.get(0).add(2);

matrix.get(1).add(3);
matrix.get(1).add(4);

matrix.get(2).add(5);
matrix.get(2).add(6);

// 출력
for (ArrayList<Integer> row : matrix) {
    for (int val : row) {
        System.out.print(val + " ");
    }
    System.out.println();
}

(참고) LinkedList 클래스

• 양방향 연결 리스트로 삽입/삭제가 빈번한 경우 유리하지만, 인덱스 접근은 느림
  (내부적으로 노드 기반)
• List<Integer> list = new LinkedList<>();
• 거의 사용하지 않음, Deque도 ArrayDeque 추천

구분	ArrayList	LinkedList
내부 구조	동적 배열 (배열 기반)	이중 연결 리스트
인덱스 접근	매우 빠름 O(1)	느림 O(N)
중간 삽입/삭제	느림 O(N)	빠름 O(1)
끝 삽입	평균 O(1) (가끔 O(N) 배열 재할당 발생)	빠름 O(1)
추가 메모리	없음	노드마다 포인터 필요
사용 예	검색, 랜덤 접근	삽입/삭제 많을 때, Deque

(참고) Stack 클래스

• 후입선출 LIFO(Last-In-First-Out) 자료구조
• Vector를 상속하기 때문에 문제점이 많아 잘 안쓰임 (대신 ArrayDeque 사용)

Stack<Integer> stack = new Stack<>();

stack.push(30);
stack.push(50);

System.out.println(stack.peek());  // 50
System.out.println(stack.isEmpty());  // false
System.out.println(stack.size());  // 2

stack.pop();  // 50
stack.pop();  // 30

C. Queue 인터페이스

FIFO (First-In, First-Out) 구조

연관 메서드

메서드	설명
boolean add(Object o)	객체를 Queue에 추가, 저장공간 부족 시 IllegalStateException 발생
Object remove()	Queue에서 객체를 꺼내 반환, 비어있을 경우 NoSuchElementException 발생
Object element()	삭제없이 요소 반환, 비어있을 경우 NosuchElementException 발생
boolean offer(Object o)	Queue에 객체 저장, 가득 차 있다면 false 반환 (예외 없음)
Object poll()	Queue에서 객체 꺼내서 반환 (기본적으로 가장 작은), 비어있을 경우 null을 반환
Object peek()	삭제없이 요소 반환, 비어있을 경우 null을 반환

시간 복잡도

자료구조	삽입/삭제 시간 복잡도	비고
LinkedList	O(1)	앞뒤 삽입/삭제 모두 빠름
ArrayDeque	Amortized O(1)	내부 배열을 재할당할 수 있음
PriorityQueue	O(log n)	힙 구조로 우선순위 유지 필요

• 일반 큐 : ArrayDeque (빠르고 효율적)
• 우선순위 큐 : PriorityQueue
• 삽입/삭제가 많거나 리스트 기능도 필요 : LinkedList

Deque 인터페이스

• Deque(Double-Ended Queue)는 양쪽 모두 삽입/삭제가 자료구조입니다.
• 스택으로 사용할 수도 있고, 큐로 사용할 수도 있습니다.
• Deque의 조상은 Queue이며, 구현체로 ArrayDeque와 LinkedList가 있습니다.

동작	앞에서	뒤에서
삽입	addFirst(e), offerFirst(e)	addLast(e), offerLast(e)
제거	removeFirst(), pollFirst()	removeLast(), pollLast()
조회	getFirst(), peekFirst()	getLast(), peekLast()

3. PriorityQueue 클래스

일반적인 큐와는 조금 다르게, 원소에 우선 순위(priority)를 부여하여 우선 순위가 높은 순으로 정렬되고 꺼냅니다.
기본 자료형의 경우 Comparable이 이미 존재하나, 사용자 정의 클래스일 경우 필수적으로 Comparable 인터페이스 또는 Comparator를 구현해야 합니다.
compareTo() 메서드 로직에 따라 자료 객체의 우선순위를 결정하는 식으로 동작되기 때문입니다.
내부적으로 힙(Heap) 구조를 사용하고, null 요소를 허용하지 않습니다.

선택 시 고려사항

• 가장 작은/큰 값을 빠르게 꺼내야 할 때 적합 (예: 다익스트라 알고리즘)
• Comparable 구현이 없다면 정렬된 순서로 저장되지는 않음 → 반복 순회 시 정렬 순서 X

기본 사용 예시 (기본 자료형 사용)

PriorityQueue<Integer> pq = new PriorityQueue<>();
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll());  // 1 (가장 작은 값 + 삭제)
System.out.println(pq.peek());  // 3 (가장 작은 값)

Comparable 구현 (사용자 정의 클래스 사용)

class Student implements Comparable<Student> {
    String name;
    int priority; // 우선순위 값

    public Student(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public int compareTo(Student u) {
        // Student의 priority값을 비교해 우선순위를 결정하여 정렬
        if (this.priority < u.priority) {
            return -1;
        } else if (this.priority == u.priority) {
            return 0;
        } else {
            return 1;
        }
    }

    // 출력 오버라이드 (구현 안하면 필드 직접 출력 해야 함 ex. s.name);
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", priority=" + priority +
                '}';
    }
}


public static void main(String[] args) {
    // 오름차순 우선순위 큐
    Queue<Student> pq = new PriorityQueue<>();

    pq.offer(new Student("주몽", 5));
    pq.offer(new Student("세종", 9));
    pq.offer(new Student("홍길동", 1));
    pq.offer(new Student("임꺽정", 2));

    // 우선순위 대로 정렬됨
    System.out.println(pq);

    // 우선순위가 가장 높은 값 참조
    System.out.println(pq.peek()); // Student{name='홍길동', priority=1}

    // 차례대로 꺼내기
    System.out.println(pq.poll()); // Student{name='홍길동', priority=1}
    System.out.println(pq.poll()); // Student{name='임꺽정', priority=2}
    System.out.println(pq.poll()); // Student{name='주몽', priority=5}
    System.out.println(pq.poll()); // Student{name='세종', priority=9}
}

Comparator 전달 (사용자 정의 클래스 사용)

class Task {
    int priority;
    public Task(int p) { this.priority = p; }
}

PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));
pq.offer(new Task(1));
pq.offer(new Task(3));
System.out.println(pq.poll().priority);  // 1

4. ArrayDeque 클래스

ArrayList와 유사하지만 배열 기반의 양방향 덱(Deque) 구현체입니다.
Stack 클래스와 대기열로 사용할 때의 LinkedList보다 빠르게 사용 가능합니다.
사이즈에 제한이 없고, null 요소는 저장되지 않습니다.

선택 시 고려사항

• 스택 또는 큐를 빠르게 구현하고 싶을 때 가장 효율적
• LinkedList보다 빠른 퍼포먼스를 제공

기본 사용 예시

Deque<Integer> dq = new ArrayDeque<>();

dq.offerLast(100); // [100]
dq.offerFirst(10); // [10, 100]
dq.offerFirst(20); // [20, 10, 100]
dq.offerLast(30); // [20, 10, 100, 30]

dq.pollFirst(); // 20 <- [10, 100, 30]
dq.pollLast(); // [10, 100] -> 30
dq.pollFirst(); // 10 <- [100]
dq.pollLast(); // [] -> 100

5. LinkedList 클래스

List, Deque, Queue 인터페이스 모두를 상속받고 있으므로, 다양한 자료구조로 응용이 가능합니다.
양방향 연결 리스트로 구성되어 있고, null 요소를 허용합니다.

선택 시 고려사항

• 중간 삽입/삭제가 많은 경우 유리
• 성능은 단순한 Queue에 비해 느릴 수 있음

기본 사용 예시

Queue<String> q = new LinkedList<>(); // Queue 타입으로 받음
Deque<String> q = new LinkedList<>(); // Deque 타입으로 받음
q.offer("A");
q.offer("B");
q.offer("C");
System.out.println(q.poll());  // "A"
System.out.println(q); // [B, C]

---

참고 블로그

• Inpa Dev - Collections Framework 총정리