[Programmers] 최댓값과 최솟값

https://school.programmers.co.kr/learn/courses/30/lessons/12939

프로그래머스

문제 설명

말 그대로 공백을 기준으로 나누어진 숫자로 구성된 문자열에서 최솟값과 최댓값을 구하면 되는 문제이다. 문제 자체가 쉽기 때문에 최댓값, 최솟값을 구하는 방법에 대해서 생각해보자.

1. 선형 탐색

단순하게 요소 모두를 탐색하면서 최댓값과 최솟값을 비교해보면 되는 방법이다. 항상 O(n)이 소요된다.

class Solution {
    public String solution(String s) {
        String[] strnums = s.split(" ");
            
        int[] nums = new int[strnums.length];
        for (int i = 0; i < strnums.length; i++) {
            nums[i] = Integer.parseInt(strnums[i]);
        }
        
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            
            if (nums[i] < min) {
                min = nums[i];
            }
        }
        
        return min + " " + max;
    }
}

2. 정렬

정렬을 통해서도 구할 수 있다. 오름차순으로 정렬한다고 하면 맨 앞 요소는 최솟값이고 맨 뒤 요소는 최댓값이다. Java에서 제공하는 정렬은 Tim Sort 이므로 최악의 경우 O(n log n)이 소요된다. 그 외에도 병합 정렬, 퀵 정렬등으로도 같은 시간복잡도로 해결할 수 있다.

import java.util.Arrays;

class Solution {
    public String solution(String s) {
        String[] strnums = s.split(" ");
            
        int[] nums = new int[strnums.length];
        for (int i = 0; i < strnums.length; i++) {
            nums[i] = Integer.parseInt(strnums[i]);
        }
        
        Arrays.sort(nums);
        
        return nums[0] + " " + nums[nums.length - 1];
    }
}

 3. 힙 자료구조

힙(Heap)은 최댓값 또는 최솟값을 빠르게 찾기 위해 개발된 일종의 이진 트리로 만들어진 자료구조이다. Java에서는 PriorityQueue가 구현체로 제공된다. 이 문제의 경우 큐에 넣는데 O(n), 다시 꺼내는데 O(n)이 소요되므로 O(2n)이다.

import java.util.PriorityQueue;

class Solution {
    public String solution(String s) {
        String[] strnums = s.split(" ");
            
        int[] nums = new int[strnums.length];
        for (int i = 0; i < strnums.length; i++) {
            nums[i] = Integer.parseInt(strnums[i]);
        }
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int num: nums) {
            pq.add(num);
        }
        
        int min = pq.poll();
        while (pq.size() != 1) {
            pq.poll();
        }
        int max = pq.poll();
        
        return min + " " + max;
    }
}