백준10818번) 최소, 최대

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

10818번: 최소, 최대

◇ 문제

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

 

◇ 입력

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

 

◇ 출력

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

 

---

◆ 풀이

배열 사용 기본 문제. 바로 풀어보도록 한다.

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int iMax = Integer.parseInt(scanner.nextLine());
        int[] array = new int[iMax];

        String[] sArray = scanner.nextLine().split(" ");
        for(int i=0; i<iMax; i++){
            array[i] = Integer.parseInt(sArray[i]);
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i=0; i<iMax; i++){
            if(array[i]<min)
                min = array[i];

            if(array[i]>max)
                max = array[i];
        }

        System.out.println(min+" "+max);
    }
}

왜 이렇게 오래 걸린 걸까?

이렇게 오래 걸린 게 마음에 들지 않아 비교 연산을 하나 줄여보았다.

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int iMax = Integer.parseInt(scanner.nextLine());
        int[] array = new int[iMax];

        String[] sArray = scanner.nextLine().split(" ");
        for(int i=0; i<iMax; i++){
            array[i] = Integer.parseInt(sArray[i]);
        }

        if(array.length > 0){
            int min = array[0];
            int max = min;
            for(int i=0; i<iMax; i++){
                if(array[i]<min)
                    min = array[i];
                else if(array[i]>max)
                    max = array[i];
            }

            System.out.println(min+" "+max);
        }
    }
}

메모리 사용이 늘어난 대신 시간이 미미하게 줄었다.

이번엔 메모리를 줄여볼까 싶어서 int를 미리 선언해보았다.

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int i=0;

        int iMax = Integer.parseInt(scanner.nextLine());
        int[] array = new int[iMax];

        String[] sArray = scanner.nextLine().split(" ");
        for(i=0; i<iMax; i++){
            array[i] = Integer.parseInt(sArray[i]);
        }

        if(array.length > 0){
            int min = array[0];
            int max = min;
            for(i=0; i<iMax; i++){
                if(array[i]<min)
                    min = array[i];
                else if(array[i]>max)
                    max = array[i];
            }

            System.out.println(min+" "+max);
        }
    }
}

예상 외로 시간도 줄었다!

객체 생성하는 것도 코스트가 꽤 되나 보다.

이제 더이상 줄일 수 있는 게 없는건가? 싶었는데 테스트 케이스가 많은 경우 자바 Scanner 클래스가 상당히 느리다는 이야기를 듣게 되었다. 그리고 다음 포스트 링크를 받았는데, (이미지 클릭 시 이동)

그러고보면 확실히 java보다는 c++이나 python으로 많이 하는 것 같다.

그래서 바로 적용해보았다!

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

public class Main {

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

        int i=0;

        StringTokenizer st = new StringTokenizer(br.readLine());
        int iMax = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] array = new int[iMax];
        for(i=0; i<iMax; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }

        if(array.length > 0){
            int min = array[0];
            int max = min;
            for(i=0; i<iMax; i++){
                if(array[i]<min)
                    min = array[i];
                else if(array[i]>max)
                    max = array[i];
            }

            System.out.println(min+" "+max);
        }
    }
}

세상에...

오늘부터는 테스트 케이스가 많은 경우에는 Scanner 사용을 일체 금할 것이다...