[백준] 10818번 : 최소, 최대 - JAVA [자바]

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

10818번: 최소, 최대

 

---

• 문제

 

매우 간단한 문제다!

※ 주의할 점

1. N 개의 정수를 공백으로 구분해서 주어진다.

 

 

---

• 3가지 풀이방법을 제시한다.

기본적으로 배열 문제인 만큼 배열을 이용한 방법을 통해 입력방법을 달리하여 Scanner 와 BufferedReader 을 통해 입력받아본다.

 

그리고 배열을 이용하지 않는 방법을 통해 풀어보고자 한다. 즉, 아래와 같다.

 

1. 배열 + Scanner
2. 배열 + BufferedReader
3. 배열 X + BufferedReader

 

 

---

• 풀이

- 방법 1 

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
        
		int N = in.nextInt();
		int[] arr = new int[N];
        
		for (int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
        
		in.close();
		Arrays.sort(arr);
		System.out.print(arr[0] + " " + arr[N - 1]);
	}
}

 

가장 기초적인 방법이다.

맨 첫줄에 N을 입력받아 해당 크기의 배열을 선언한 뒤 arr 배열 원소에 각각 입력받은 값을 넣어주는 방법이다.

 

그리고 최댓값과 최솟값을 찾는 방법은 매우 쉽다.

우리에겐 Arrays.sort() 라는 메소드가 있다.

 

이 메소드는 배열에 저장된 원소 값을 오름차순으로 정렬해주는 메소드다.

이 메소드를 활용하여 정렬하면 최솟값은 배열의 첫번째 원소(index 0)에, 최댓값은 배열의 마지막 원소(arr.length-1)에 있을테니 이를 출력하면 된다.

 

( 물론 정렬할 필요 없이 방법 3처럼 원소 하나씩 꺼내와서 써도 된다. - 아래 방법3 참고 )

 

 

 

 

 

---

 

- 방법 2 

 

BufferedReader 을 쓰는 방식이다.

 

readLine() 을 통해 입력 받기 때문에 공백도 같이 입력되니 StringTokenizer를 통해 분리해주려 한다.

나머지 알고리즘은 똑같다.

 

그리고 반드시 자료형 타입을 잘 보아야 한다.

st.nextToken() 은 문자열을 반환하니 Integer.parseInt()로 int 형으로 변환시켜준다.

 

import java.util.Arrays;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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 index = 0;
		int[] arr = new int[N];
		while(st.hasMoreTokens()) {
			arr[index] = Integer.parseInt(st.nextToken());
			index++;
		}
		
		Arrays.sort(arr);
		System.out.print(arr[0] + " " + arr[N - 1]);
	}
}

 

보다시피 일단 입력받은 정수들을 배열에 저장하기 위해서 StringToken 에 들어있는 모든 토큰들이 없어질 때까지 배열에 모두 담는다.

(참고로 hasMoreTokens() 는 StringTokenizer 에 토큰이 남아있으면 true, 비어있으면 false를 반환한다.)

 

 

 

 

---

- 방법 3

근데 배열을 굳이 써줄 필요가 있을까? 메모리만 잡아먹고, 배열의 원소 정렬에서 최악의 경우 시간복잡도가 N^2 이기 때문에 너무 불필요하게 시간을 낭비한다.

 

그러면 어떻게 하면 시간하고 메모리를 적게 낭비시킬까?

이에 대한 해결은 다음 두 가지를 통해 대부분 해결할 수 있다.

 

1. 배열을 사용하지 않는다.
2. 입력받은 문자를 즉시 비교한다. ( 그러면 시간복잡도가 N 으로 정렬할 필요 없어 시간을 단축시킬 수 있음 )

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수라고 되어있기 때문에 비교를 위해 max 에는 가장 작은 값으로, min 에는 가장 큰 값으로 초기화를 해준다.

 

그리고 반복문에서 각 토큰을 가져와 기존 max 의 값보다 큰지, 기존 min 의 값보다 작은지 비교하면서 수행하면 된다.

 

 

 

 

 

---

• 성능 차이
  

 

위에서 부터 순서대로

 

채점 번호 : 17995776  -  BufferedReader + 배열 X

채점 번호 : 17995764  -  BufferedReader + 배열

채점 번호 : 17995743  -  Scanner  + 배열

 

 

보면 바로 알 수 있듯이 입력 방법에서 Scanner 와 BufferedReader 의 메모리, 시간 차이는 어마어마하다.

 

또한 배열을 사용하면 최악의 경우 시간복잡도가 O(N^2) 이지만 배열을 사용하지 않고 즉시 비교하는 경우 시간복잡도가 O(N) 이므로 훨씬 시간이 단축되는 것을 볼 수 있다.

 

 

 

 

 

---

• 정리

알고리즘을 풀 때 물론 해당 조건대로 풀지 않아도 푸는 방법이야 많다.

그러나 일단 기본적으로 배열 목록의 문제인 만큼 배열을 이용하여 풀이를 하고, 그 다음에 배열을 이용하지 않고 풀어볼 수 있으면 그 때 다른 알고리즘으로 풀어보는 것이 좋다고 생각한다.

 

또한 배열을 굳이 정렬을 하지 않고도 배열 원소를 검사하여 할 수도 있다.

 

즉, 여러분들이 알고리즘을 구성할 때 시간복잡도와 특정 메소드, 생성자 등 다양한 요성들을 고려하여 최선의 시간복잡도를 찾아보는 것이 중요하다.