Your Name

I am an amazing person.

1 분 소요

문제 설명

프로그래머스 181853번 뒤에서 5등까지

정수로 이루어진 리스트 num_list가 주어집니다. num_list에서 가장 작은 5개의 수를 오름차순으로 담은 리스트를 return하도록 solution 함수를 완성해주세요.

제한 사항

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

입출력 예시

num_list result
[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]가 됩니다.

코드 구현

Python

def solution(num_list):
    num_list.sort()
    return num_list[:5]

시간 복잡도 - Python

  • 리스트를 오름차순으로 정렬 → $O(\log(n))$
  • 처음 5개 요소 슬라이싱 → $O(1)$
  • 따라서, 총 시간 복잡도는 $O(\log(n))$이다.

개선할 점 - Python

  • 힙을 사용하면 불필요한 정렬을 하지 않아 데이터가 클수록 시간 복잡도가 $O(n)$에 가까워진다.
import heapq

def solution(num_list):
    return heapq.nsmallest(5, num_list)

Java

import java.util.Arrays;

class Solution {
    public int[] solution(int[] num_list) {
        int[] answer = new int[5];
        Arrays.sort(num_list);
        System.arraycopy(num_list, 0, answer, 0, answer.length);
        return answer;
    }
}

시간 복잡도 - Java

  • 배열을 오름차순으로 정렬 → $O(\log(n))$
  • 처음 5개 요소 복사 → $O(1)$
  • 따라서, 총 시간 복잡도는 $O(\log(n))$이다.

개선할 점 - Java

  • 우선순위 큐를 사용하여 최소 힙을 유지해 시간 복잡도를 $O(n)$에 가깝게 유지할 수 있다.
import java.util.PriorityQueue;

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

        int[] answer = new int[5];
        for (int i = 0; i < 5; i++) {
            answer[i] = minHeap.poll();  // 최소값 5개 추출
        }
        
        return answer;
    }
}

참고