[백준] 입출력 - 10818 최대, 최소 (서칭)

* 공부 목표

입출력 - 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992

 

** 혼자 풀이의 문제

- 값을 비교하여 최대값을 대체하는 for문에 빠져서 단순한 풀이를 놓쳤음. 결국 답안 서칭.

- 메소드 쓸 수 있는 건 바로 쓰자.

- 값 대체하려면 변수로 최대, 최소값 설정해두고 들어가면 된다.

 ▶ 그래도 덕분에, 입력하자마자 비교하는 풀이 이해할 수 있었음.

 

• 10818번

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

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

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

 

1) Scanner 활용 // 이렇게 제출하니, 메모리-시간이 역대급으로 길었음. 왜???

 1-1. Arrays.sort() 메소드 : 오름차순 정렬.

import java.util.*;

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

 

 1-2. for문 활용

import java.util.*;

public class Main{
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] num = new int[N];
		int max = -1000001;
		int min = 1000001;
		for(int i=0; i<N; i++) {
			num[i] = sc.nextInt();
			if(num[i] > max) {
				max = num[i];
			}
			if (num[i] < min) {
				min = num[i];
			}
		}
        sc.close();
		System.out.println(min + " " + max);
	}
}

 

 

2. bufferedReader 활용 //메모리와 시간 모두 절반 이하로 떨어짐. 왜???

 

import java.util.*;
import java.io.*;

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 max = -1000001;
		int min = 1000001;
		while(st.hasMoreTokens()) {
			int Value = Integer.parseInt(st.nextToken());
			if(Value > max) {
				max = Value;
			}
			if (Value < min) {
				min = Value;
			}
		}
        br.close();
		System.out.println(min + " " + max);
	}
}

 

 

메모리와 시간이 차이 났던 이유는

첫째, scanner와 bufferedReader의 차이. 둘째, <배열>이었다.

 

답안 서칭하면서 참고한 블로그 내용의 일부를 발췌해 왔다.

배열을 사용하는 최악의 경우, 시간 복잡도가 O(N^2)이지만, 즉시 비교하는 경우(배열 미사용), 시간 복잡도가 O(N)이므로 훨씬 시간이 단축되는 것을 확인할 수 있다.

https://d2.naver.com/helloworld/0315536

 

배열은 정렬했을 때 최악이 O(N^2)까지 나오지만,

while문으로 바로 입력받으면 최대 O(log N) - 최소 O(N) 이기 때문이라고 이해했다.

(시간 복잡도 계산하는 법을 몰라 정확하지 않을 수 있습니다.)

 

* 시간 복잡도 순위 (낮을 수록 좋다.)

O(1) < O( log n ) < O(n) < O(n log n) < O(n^2) < O(n^3)

 

빅오 복잡도 그래프

 

[참고] https://st-lab.tistory.com/43