[백준] 최소,최대_10818_자바

10818번 Java-최소, 최대

---

이번 문제의 분류는 <1차원 배열>입니다.

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

10818번: 최소, 최대

---

1. 문제

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

 

---

2. 예제

---

3. 풀이

이번 문제는 간단한 문제입니다. 따라서 저는 다양한 방법으로 풀어보며 수행 속도를 비교해보았습니다.

---

- 방법 1

Scanner 활용, 시간 복잡도 O(n) 수행 방법

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt(); // 비교할 수의 개수
        int[] arr = new int[count];
        int min = 0; // 최솟값
        int max = 0; // 최댓값

        for(int i=0; i<arr.length;i++) {
            int val = sc.nextInt(); // 수 입력
            arr[i] = val;
            min = arr[0]; // 최솟값을 배열 인덱스 0으로 초기화
            max = arr[0]; // 최댓값을 배열 인덱스 0으로 초기화
        }

        for(int i=0; i<arr.length;i++){

			// 현재 최솟값이 arr[i]보다 큰지 여부 체크
            if(min > arr[i]) {
                min = arr[i]; // 크다면 arr[i]을 min으로 삽입
            }

			// 현재 최댓값이 arr[i]보다 작은지 여부 체크
            if(max < arr[i]) {
                max = arr[i]; // 작다면 arr[i]을 max로 삽입
            }
        }

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

1) if문을 두 번 사용하면서 최솟값과 최댓값을 동시에 찾게 합니다.

2) for문이 모두 돌면(배열 내의 수만큼 검색하면) 최솟값과 최댓값을 찾게 됩니다. 따라서 O(N)의 수행 속도를 갖게 됩니다.

---

- 방법 2

BufferedReader, StringTokenizer 활용

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 count = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int[] arr = new int[count];
        int min = 0;
        int max = 0;

        for(int i=0; i<arr.length;i++) {
            int val = Integer.parseInt(st.nextToken());
            arr[i] = val;
            min = arr[0];
            max = arr[0];
        }

        for(int i=0; i<arr.length;i++){

            if(min > arr[i]) {
                min = arr[i];
            }

            if(max < arr[i]) {
                max = arr[i];
            }
        }

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

}

1) 입력 방식을 바꾼 것 외, 내용은 방법1과 동일

---

- 방법 3

java.utill.Arrays 클래스 활용, 정렬 후 출력

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 count = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int index = 0; // for문이 아닌 while을 활용할 것이기 때문에 index 지정
        int[] arr = new int[count];

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

        Arrays.sort(arr); // arr 배열을 Array 자바 패키지를 통해 정렬
        System.out.println(arr[0] + " " + arr[count-1]); // 정렬된 수에서 0번, 맨끝 인덱스 출력
    }
}

1) hasMoreTokens( ) : StringTokenizer에 사용할 수 있는 토큰이 더 있는지 확인하는 메소드입니다.

2) java.util의 Arrays 클래스 활용, 클래스 내의 sort 메소드를 통해 배열을 순서에 맞게 정렬합니다. 

3) 배열이 (어센딩으로) 정렬되었기 때문에 0번째 인덱스가 최솟값, 마지막 인덱스가 최댓값이 됩니다.

---

- 방법 4

배열을 사용하지 않고, 입력한 즉시 수를 비교하는 방식
참고 : [Stranger's LAB] https://st-lab.tistory.com/43

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));

        Integer.parseInt(br.readLine());	//첫 줄 N 은 안쓰이므로 입력만 받는다.
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int max = -1000001; // 최소 정수값 지정
        int min = 1000001; // 최대 정수값 지정

        while(st.hasMoreTokens()) {
            int val = Integer.parseInt(st.nextToken());
            if(val>max) {
                max = val;
            }
            if(val<min) {
                min = val;
            }
        }
        System.out.println(min + " " + max);
    }
}

1) 원리는 위에서 설명한 방법 1, 방법 2와 유사합니다.

2) 배열을 사용하지 않고, 숫자를 입력받는 즉시 최소, 최대를 비교하여 각 변수에 삽입하는 방식입니다.

3) 오로지 배열을 활용하여 문제를 해결하려고 했으나, 위 같이 배열을 사용하지 않고도 풀 수 있다는 것을 알게 되었습니다.

---

4. 결론

• 제출 번호 38417583 : 배열 X, BufferedReader
• 제출 번호 38417289 : Arrays 클래스, BufferedReader
• 제출 번호 38417021 : BufferedReader
• 제출 번호 38416734 : Scanner

---

Arrays 클래스를 활용했을 때는 정렬을 진행해서 시간이 비교적 걸린 것이라고 생각됩니다.

그리고 이제는 BufferedReader을 활용했을 때, 수행 속도가 빨라진다는 것을 확실하게 알았습니다.

그리고 한 문제를 다양한 방법으로 풀 수 있다는 것도 알았습니다.

추가적으로 java에서 제공하는 자료구조 클래스에 대해서 정리해야겠습니다.

---

 사용 클래스 및 메소드

• java.util.Scanner
• java.io.BufferedReader.readLine()
• java.io.InputStreamReader
• java.util.StringTokenizer.nextToken()
• java.util.StringTokenizer.hasMoreTokens()
• java.util.Arrays.sort()