Coding Test

CT | Java에서 효율적으로 ArrayList에서 최대값을 찾고 제거하기(백준 - 11279)

이진유진 2024. 8. 27. 18:39
반응형

서론

Java에서 ArrayList를 사용해 데이터를 처리할 때, 종종 가장 큰 값을 찾고 이를 제거하는 작업을 해야 할 때가 있습니다.

간단하게 ArrayList와 Collections를 사용하여 구현할 수 있지만, 큰 데이터셋을 다룰 때 성능 문제가 발생할 수 있습니다.

이 글에서는 ArrayList를 사용한 기본 접근 방식과 성능을 개선할 수 있는 방법을 비교해보겠습니다.

문제 정의

우리는 정수 리스트에서 사용자가 0을 입력할 때마다 현재 리스트에서 가장 큰 값을 출력하고, 그 값을 리스트에서 제거하는 프로그램을 작성하려고 합니다. 사용자가 0이 아닌 값을 입력하면, 리스트에 그 값을 추가합니다. 이 작업을 효율적으로 처리하는 방법을 탐구해보겠습니다.

 

백준 : 최대 힙 문제 | 11279

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

기본 접근 방식: ArrayList와 Collections.max()

처음에 작성한 코드는 다음과 같습니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        ArrayList<Integer> a = new ArrayList<>();
        scanner.nextLine();

        for (int i = 0; i < n; i++) {
            int input = scanner.nextInt();

            if(input == 0) {
                if(a.isEmpty()) {
                    System.out.println(0);
                } else {
                    int max = Collections.max(a);
                    System.out.println(max);
                    int indexToRemove = a.indexOf(max);
                    if (indexToRemove != -1) {
                        a.remove(indexToRemove);
                    }
                }
            } else {
                a.add(input);
            }
        }

        scanner.close();
    }
}

 

이 코드의 동작 방식은 다음과 같습니다:

  1. 사용자가 값을 입력하면, ArrayList에 추가합니다.
  2. 사용자가 0을 입력하면, 리스트에서 가장 큰 값을 찾고 출력한 다음, 그 값을 리스트에서 제거합니다.

문제점: 시간 복잡도

이 접근 방식에서는 Collections.max() 메소드를 호출하여 최대값을 찾고, indexOf() 메소드를 사용하여 해당 값을 제거합니다.

그러나 이 두 작업 모두 O(n)의 시간 복잡도를 가지므로, 큰 리스트에서는 성능이 저하될 수 있습니다.

특히, 반복적으로 최대값을 찾고 제거하는 경우 성능 문제는 더욱 두드러집니다.

개선된 접근 방식: PriorityQueue 사용

성능 문제를 해결하기 위해 PriorityQueue를 사용할 수 있습니다.

PriorityQueue는 힙(Heap) 자료구조로 구현되어 있으며, 자동으로 정렬을 유지하기 때문에 최대값을 효율적으로 찾고 제거할 수 있습니다.

아래는 PriorityQueue를 사용한 개선된 코드입니다:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // 우선순위 큐를 사용하여 최대값을 관리
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        scanner.nextLine();

        for (int i = 0; i < n; i++) {
            int input = scanner.nextInt();

            if(input == 0) {
                if(maxHeap.isEmpty()) {
                    System.out.println(0);
                } else {
                    int max = maxHeap.poll(); // 큐에서 최대값 꺼내기
                    System.out.println(max);
                }
            } else {
                maxHeap.add(input); // 큐에 값 추가
            }
        }

        scanner.close();
    }
}

* Collections.reverseOrder()는 Java에서 기본 정렬 순서를 반대로 바꾸는 데 사용되는 메서드입니다.
기본적으로 Java의 PriorityQueue는 최소 힙(Min-Heap)으로 동작하며, 가장 작은 값이 우선 순위가 높습니다.
즉, PriorityQueue를 사용할 때 기본적으로 작은 값이 먼저 나옵니다.

하지만, 우리가 PriorityQueue를 최대 힙(Max-Heap)으로 사용하고 싶을 때는 기본 정렬 순서를 반대로 바꿔야 합니다.
이때 Collections.reverseOrder() 메서드를 사용하여 Comparator를 반환받을 수 있습니다.
이 Comparator는 기본 정렬 순서를 뒤집어, 큰 값이 우선 순위를 가지도록 만듭니다.

 

이 코드에서는 다음과 같은 방식으로 문제를 해결합니다:

  1. PriorityQueue를 최대 힙으로 사용하여, 값을 추가할 때마다 자동으로 정렬합니다.
  2. 사용자가 0을 입력할 때 poll() 메소드를 호출하여 큐에서 가장 큰 값을 효율적으로 꺼내고 제거합니다.

장점: 시간 복잡도 개선

이 접근 방식에서는 삽입(add)과 제거(poll) 연산이 O(log n)의 시간 복잡도를 가지므로, 큰 리스트에서도 효율적으로 동작합니다.

결론

ArrayList와 Collections.max()를 사용한 기본 접근 방식은 간단하고 이해하기 쉽지만, 큰 데이터셋을 처리할 때는 성능 문제가 발생할 수 있습니다.

이 문제를 해결하기 위해 PriorityQueue를 사용하면 시간 복잡도를 크게 개선할 수 있으며, 더 큰 입력에 대해서도 성능을 유지할 수 있습니다.

Java에서 효율적인 데이터 처리를 위해서는 문제의 특성과 데이터의 크기에 따라 적절한 자료구조를 선택하는 것이 중요합니다.

이 글이 여러분의 코드 최적화에 도움이 되기를 바랍니다.

반응형