[프로그래머스] 뒤에서 5등까지

뒤에서 5등까지 - 알고리즘 문제 풀이 (Java & Python)

이번 글에서는 정수로 이루어진 리스트 num_list에서 가장 작은 5개의 수를 오름차순으로 반환하는 문제를 풀어보겠습니다. Java와 Python으로 문제를 해결해보고, 각각의 풀이 방법에 대한 시간 및 공간 복잡도를 분석한 후, 다양한 Java 풀이 방법과 그에 대한 비교를 설명드리겠습니다.

문제 설명

정수로 이루어진 리스트 num_list가 주어집니다. 이 리스트에서 가장 작은 5개의 수를 오름차순으로 담은 리스트를 반환하는 solution 함수를 구현하세요.

제한사항

• 6 ≤ num_list의 길이 ≤ 30
• 1 ≤ num_list의 원소 ≤ 100

입출력 예

num_list	결과
[12, 4, 15, 46, 38, 1, 14]	[1, 4, 12, 14, 15]

입출력 예 #1: [12, 4, 15, 46, 38, 1, 14]를 정렬하면 [1, 4, 12, 14, 15, 38, 46]이 되고, 앞에서부터 5개를 고르면 [1, 4, 12, 14, 15]가 됩니다.

해결 방법

이 문제를 해결하기 위해 리스트를 정렬한 후 가장 작은 5개의 수를 추출합니다. 각각의 언어(Java, Python)로 코드와 설명을 제공하며, 시간 및 공간 복잡도를 분석하겠습니다.

Python 코드

def solution(num_list):
    # 리스트를 오름차순으로 정렬하고, 가장 작은 5개의 수를 반환
    return sorted(num_list)[:5]

시간 및 공간 복잡도

• 시간 복잡도: O(n log n) - 리스트를 정렬하는 데 걸리는 시간입니다. 여기서 n은 num_list의 길이입니다.
• 공간 복잡도: O(n) - 정렬 과정에서 추가적인 공간이 필요하며, 결과 리스트를 저장하기 위한 공간도 필요합니다.

Java 코드

import java.util.Arrays;

class Solution {
    public int[] solution(int[] num_list) {
        // 배열을 오름차순으로 정렬
        Arrays.sort(num_list);

        // 가장 작은 5개의 원소를 반환
        return Arrays.copyOfRange(num_list, 0, 5);
    }
}

시간 및 공간 복잡도

• 시간 복잡도: O(n log n) - 배열을 정렬하는 데 걸리는 시간입니다. 여기서 n은 num_list의 길이입니다.
• 공간 복잡도: O(n) - 정렬 과정에서 추가적인 메모리가 사용되며, 결과 배열을 저장하기 위한 공간도 필요합니다.

다양한 Java 풀이 방법 소개

위의 기본 풀이 외에도 자바에서는 다양한 방법으로 이 문제를 해결할 수 있습니다. 몇 가지 추가적인 풀이 방법을 살펴보겠습니다.

1. 우선순위 큐(Priority Queue) 사용

Java의 PriorityQueue를 사용하여 가장 작은 5개의 수를 찾을 수 있습니다.

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int[] solution(int[] num_list) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : num_list) {
            minHeap.add(num);
        }

        int[] result = new int[5];
        for (int i = 0; i < 5; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }
}

설명

• 우선순위 큐 사용: PriorityQueue는 기본적으로 최소 힙(min heap)으로 구현되어 있어, 원소를 추가할 때마다 자동으로 정렬됩니다.
• 작은 값 추출: poll()을 사용하여 가장 작은 값들을 차례로 추출합니다.

장점 및 단점

• 장점: 큰 배열에서 상위 몇 개의 원소를 추출할 때 유리합니다.
• 단점: 전체 정렬보다 복잡한 방법이며, 추가적인 데이터 구조 사용으로 메모리 오버헤드가 발생할 수 있습니다.

2. Stream API 사용

Java 8 이상의 버전에서는 Stream API를 이용하여 간결하게 문제를 해결할 수 있습니다.

import java.util.Arrays;
import java.util.stream.IntStream;

class Solution {
    public int[] solution(int[] num_list) {
        return IntStream.of(num_list)
                        .sorted()
                        .limit(5)
                        .toArray();
    }
}

설명

• Stream 사용: IntStream.of(num_list)를 통해 배열을 스트림으로 변환하고, sorted() 메서드를 이용해 정렬한 후, limit(5)로 상위 5개의 원소를 추출합니다.
• 간결함: 코드가 간결하며 직관적입니다.

장점 및 단점

• 장점: 코드가 간결하고, 함수형 스타일로 작성되어 가독성이 높습니다.
• 단점: 작은 배열에서는 성능 차이가 없지만, 스트림 사용에 따른 약간의 성능 오버헤드가 발생할 수 있습니다.

비교 및 결론

• 기본 Arrays.sort() 사용: 가장 직관적이며 간단한 방법으로, 배열의 크기가 작을 때 유리합니다.
• 우선순위 큐 사용: 큰 데이터에서 상위 몇 개의 원소를 빠르게 추출할 때 유리하지만, 작은 배열에서는 불필요한 오버헤드가 발생할 수 있습니다.
• Stream API 사용: 함수형 프로그래밍 스타일로 코드가 간결하며 가독성이 높지만, 내부적으로 반복자를 사용하므로 성능 오버헤드가 발생할 수 있습니다.

응용 문제

만약 오름차순이 아닌 내림차순으로 한다면?

Python 코드

def solution(num_list):
    # 리스트를 오름차순으로 정렬하고, 가장 작은 5개의 수를 추출한 뒤, 내림차순으로 정렬하여 반환
    return sorted(sorted(num_list)[:5], reverse=True)

Java 코드

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int[] solution(int[] num_list) {
        return Arrays.stream(num_list)
                     .boxed()  // int -> Integer로 변환
                     .sorted(Collections.reverseOrder())  // 내림차순 정렬
                     .limit(5)  // 상위 5개 추출
                     .mapToInt(Integer::intValue)  // Integer -> int로 변환
                     .toArray();  // int[] 배열로 변환

    }
}

1. 우선순위 큐(Priority Queue) 사용

Java의 PriorityQueue를 사용하여 가장 작은 5개의 수를 찾은 후, 내림차순으로 정렬할 수 있습니다.

import java.util.PriorityQueue;
import java.util.Collections;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> solution(int[] num_list) {
        // 내림차순 우선순위 큐 (최대 힙)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // num_list 배열의 모든 요소를 큐에 삽입
        for (int num : num_list) {
            maxHeap.add(num);
        }

        // 큐에서 상위 5개의 값을 추출하여 배열로 변환
        int[] result = new int[5];
        for (int i = 0; i < 5; i++) {
            result[i] = maxHeap.poll();  // 큐에서 값을 꺼내서 배열에 저장
        }

        // 이미 큐에서 꺼낸 값들이 내림차순이므로 별도의 정렬은 필요 없음
        return result;
    }
}

설명

• 우선순위 큐 사용: PriorityQueue는 기본적으로 최소 힙(min heap)으로 구현되어 있어, 원소를 추가할 때마다 자동으로 정렬됩니다.
• 작은 값 추출: poll()을 사용하여 가장 작은 값들을 차례로 추출한 후, 결과를 내림차순으로 정렬합니다.

장점 및 단점

• 장점: 큰 배열에서 상위 몇 개의 원소를 추출할 때 유리합니다.
• 단점: 전체 정렬보다 복잡한 방법이며, 추가적인 데이터 구조 사용으로 메모리 오버헤드가 발생할 수 있습니다.

문제의 제한 조건(배열의 길이가 최대 30)에 비추어 볼 때, 각 방법의 성능 차이는 거의 없으며, 개인의 선호도와 코드 스타일에 따라 선택하면 됩니다. 간결한 코드를 원한다면 Stream API를, 명시적인 데이터 구조 활용을 원한다면 우선순위 큐를 사용하는 것이 좋습니다.

이 글을 통해 배열의 가장 작은 5개의 원소를 추출하는 문제를 다양한 방식으로 해결해 보았습니다. 여러분의 상황에 맞는 방법을 선택하여 효율적으로 문제를 해결해 보세요! 😊