Baekjoon(JAVA) - Algorithm] 10818번: 최소, 최대

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

10818번: 최소, 최대

 

---

Answer 1

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

public class Main {
    public static void main(String[] args) {
        int minNum = 1000000;
        int maxNum = -1000000;

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int[] numbers = new int[N];
            for (int i = 0; i < N; i++) {
                numbers[i] = Integer.parseInt(st.nextToken());
            }

            for (int number : numbers) {
                if (minNum > number) {
                    minNum = number;
                }

                if (maxNum < number) {
                    maxNum = number;
                }
            }
        } catch (IOException e) {
            System.err.println("ERROR = " + e.getMessage());
        }

        System.out.println(minNum + " " + maxNum);
    }
}

배열을 사용해서 풀었다.

 

Code Review 1

int minNum = 1000000;
int maxNum = -1000000;

지문에서 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같다고 하므로 비교할 수 있도록 `minNum` 최솟값에 1000000을, `maxNum` 최댓값에 -1000000을 선언했다.

 

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    ...
} catch (IOException e) {
    System.err.println("ERROR = " + e.getMessage());
}

`try-with-resoures`로 try문에 객체의 자원을 받아서 try문이 끝나면 그 자원을 따로 `br.close()`를 하지 않고 반환한다.

`System.in`으로 사용자로부터 입력받은 데이터를 바이트 스트림으로 받는다.

`InputStreamReader` 클래스로 바이트 스트림을 문자 기반 스트림으로 변환한다.

`BufferedReader` 클래스로 문자 스트림을 읽는다.

 

이제 try문 안의 로직을 살펴보자.

int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");

문자열의 첫째 줄인 N개의 정수를 입력받아 `Integer.parseInt()`로 정수 변환하여 `N` 변수를 선언한다.

`StringTokenizer` 객체를 생성한다. 이때 인자는 둘째 줄에 입력받은 N개의 정수를 문자열과 공백 구분자로 한다.

 

int[] numbers = new int[N];
for (int i = 0; i < N; i++) {
    numbers[i] = Integer.parseInt(st.nextToken());
}

N개의 정수를 알았으므로 int 타입의 배열을 N크기로 선언한다.

for문을 N만큼 반복하여 `st.nextToken()`으로 둘째 줄의 정수들을 공백으로 구분한 하나하나의 정수 문자를 `Integer.parseInt()` 정수 타입으로 변환 후 `numbers`배열에 차례로 넣는다.

 

for (int number : numbers) {
    if (minNum > number) {
        minNum = number;
    }

    if (maxNum < number) {
        maxNum = number;
    }
}

`numbers`배열을 향상된 for문으로 반복한다.

`minNum`이 현재 `number`보다 크면 `number`를 `minNum`에 대입하고,

`maxNum`이 현재 `number`보다 작으면 `number`를 `maxNum`에 대입한다.

 

System.out.println(minNum + " " + maxNum);

try문 안의 로직이 끝나고 최소 최대 값을 출력한다.

---

 

Answer 2

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

public class Main {
    public static void main(String[] args) {
        int minNum = 1000000;
        int maxNum = -1000000;

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int currentNum = 0;
            for (int i = 0; i < N; i++) {
                currentNum = Integer.parseInt(st.nextToken());
                if (minNum > currentNum) {
                    minNum = currentNum;
                }

                if (maxNum < currentNum) {
                    maxNum = currentNum;
                }
            }
        } catch (IOException e) {
            System.err.println("ERROR = " + e.getMessage());
        }

        System.out.println(minNum + " " + maxNum);
    }
}

배열을 사용하지 않고 풀었다.

 

Code Review 2

Answer 1과 중복된 부분은 Code Review 1에서 다뤘으므로 다른 부분만 정리한다.

 

int currentNum = 0;
for (int i = 0; i < N; i++) {
    currentNum = Integer.parseInt(st.nextToken());
    if (minNum > currentNum) {
        minNum = currentNum;
    }

    if (maxNum < currentNum) {
        maxNum = currentNum;
    }
}

비교에 필요한 `currentNum` 현재값을 선언한다.

for문으로 정수 N개만큼 아래 로직을 반복한다.

 

`currentNum`에 둘째 줄에서 입력받은 정수들을 공백으로 나눈 `StringTokenizer` 객체를 사용하여 `st.nextToken()`으로 하나씩 뽑아서 `Integer.parseInt()`로 정수 변환하여 대입한다.

`minNum`이 현재 `currentNum`보다 크면 `number`를 `currentNum`에 대입하고,

`maxNum`이 현재 `currentNum`보다 작으면 `number`를 `currentNum`에 대입한다.

---

 

Result

위에서부터 Answer2(배열 사용O), Answer1(배열 사용X)

확실히 배열을 사용하지 않은 풀이의 성능이 좀 더 좋다.

 

배열을 사용하면 최악의 경우 시간복잡도가 O(N^2)이다.

• 선택 정렬인 경우
  • 매 반복마다 최솟값(또는 최댓값)을 찾아서 위치를 바꾸는 과정을 반복하여 정렬을 수행하는데 이 과정에서 배열의 길이에 비례한느 비교와 교환 연산이 이루어지기 때문이다.
• 삽입 정렬인 경우
  • 각 요소를 적절한 위치에 삽입하여 정렬하는 방식으로 동작하는 과정에서 배열의 길이에 비례하는 비교와 이동 연산이 이루어지기 때문이다.

즉, 배열의 모든 요소를 반복하여 비교하고 이동하기 때문에 배열이 크기가 N일 때 최악의 경우 N^2에 비례하는 시간이 소요된다.

 

반면에 배열을 사용하지 않으면 숫자를 하나하나 바로 비교하기 때문에 시간복잡도가 O(N)이다.