https://www.acmicpc.net/problem/10818
문제
풀이
👉 배열을 사용하는 방법
StringTokenizer.hasMoreTokens() 메소드는 다음에 읽어 들일 token이 있으면 true, 없으면 false를 return 한다.
Arrays.sort() 메소드는 배열을 오름차순으로 정렬해 준다.
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[] arr = new int[n];
int index = 0;
while (st.hasMoreTokens()) { // 다음에 읽을 값이 있으면 treu, 없으면 false
arr[index] = Integer.parseInt(st.nextToken());
index++;
}
Arrays.sort(arr);
System.out.println(arr[0] + " " + arr[n-1]);
}
}
👉 배열을 사용하지 않는 방법 → 입력받은 문자를 즉시 비교
문제를 보면, 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수라고 되어있으므로
비교를 위해 max 에는 가장 작은 값으로, min 에는 가장 큰 값으로 초기화를 해준다. 그리고 while문을 통해 각 값을 가져와 비교해 주면 된다.
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));
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);
}
}
성능 비교
- 배열 사용 O : 최악의 경우 시간 복잡도 O(N^2)
- 배열 사용 X : 시간 복잡도 O(N)
배열을 사용하지 않을 때 시간이 훨씬 단축되는 것을 볼 수 있다.