[BOJ / Java] 10818 - 최소, 최대

10818번: 최소, 최대

문제

N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.

출력

첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.

풀이

첫 번째 방법 : BufferedReader + Array

주어진 수 n 크기의 배열을 만든 뒤에 숫자를 채워 넣고 정렬해서 출력한다.

package P10818;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int idx = 0;
        int[] arr = new int[n];

        while(st.hasMoreTokens()) {
            arr[idx] = Integer.parseInt(st.nextToken());
            idx++;
        }

        Arrays.sort(arr);
        br.close();
        System.out.printf("%d %d", arr[0], arr[n-1]);
    }
}

두 번째 방법 : 배열을 사용하지 않기

배열을 사용하게 되면 메모리를 할당해야 하고, 정렬할 때에도 시간이 걸린다는 문제가 있다.

dual pivot quicksort 를 사용한 자바의 내장 정렬 함수 Arrays.sort()는 quicksort가 정렬되어 있던 상태였다면 N^2의 시간 복잡도를 가지는 문제를 보완하고 속도가 더 빠르다는 것을 알았다.
dual pivot이란 이름 그대로 피벗을 두 개 사용해서 정렬한다.

그러나 최악의 경우에 N^2가 나오는 것은 해결되지 않았음!

그렇다면 min 값, max값을 하나씩 두고 받을 때마다 갱신해 버린 뒤, 바로 출력해 버리면 된다.

 

아래는 주어진 범위 1 ~ 1,000,000을 침범하지 않는 선에서 min max 값을 설정한 뒤 받으면서 계산하는 코드이다.

package P10818;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int min = 1000001;
        int max = -1000001;
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        while (st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        br.close();
        System.out.printf("%d %d",min, max);
    }
}

결과

배열을 사용하지 않는 경우의 시간이 확연하게 빠르다는 것을 알 수 있다. (그 와중 킹갓 파이썬의 코드 길이와 속도..)