[백준] 10818번 : 최소, 최대 - (C++)

---

문제

---

첫 번째 풀이 - 배열 사용

for문을 통해 array에 입력받은 값을 저장하고, sort() 함수를 이용해 오름차순으로 정렬해 최솟값, 최댓값을 구한다.

---

개념

• <algorithm> 라이브러리의 sort( begin, end) 함수

• 정렬 알고리즘, 시간 복잡도: NlogN
• 첫 번째 인자: 배열의 포인터
• 두 번째 인자: 배열의 포인터 + 배열의 크기
• 세 번째 인자: 오름차순, 내림차순을 결정하며, defalut 값은 오름차순

---

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int array[1000001];
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> array[i];
	}

	sort(array, array + n);

	cout << array[0] << " " << array[n - 1];

	return 0;
}

---

두 번째 풀이 - 배열 사용 X

for문을 통해 값을 입력받고, if문을 통해 입력 값 input이 최솟값 min보다 작다면, min을 input으로 갱신시킨다.

 

입력 값 input이 최댓값 max보다 크다면, max를 input으로 갱신시킨다.

 

따라서, min과 max를 선언할 때, 갱신이 될 수 있도록 범위 밖의 값인 1000001, -1000001로 초기화시켜야 한다.

 

 +  <algorithm> 라이브러리의 min(), max() 함수를 이용하는 것도 가능하다.

 

minV = min(minV, inputV)
maxV = max(maxV, inputV)

---

코드

#include <iostream>
using namespace std;

int main() {
	int min = 1000001;
	int max = -1000001;
	int n, input;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> input;

		if (input < min) {
			min = input;
		}

		if (input > max) {
			max = input;
		}
	}

	cout << min << " " << max;

	return 0;
}

---

결과

위에서부터 차례대로 두 번째 풀이(배열 사용 X) → 첫 번째 풀이 (배열 사용)이다.

 

• 첫 번째 풀이(배열 사용) - 배열 입력(N번) → 배열 정렬(NlogN):  시간복잡도 NlogN
• 두 번째 풀이(배열 사용 X) - 배열 입력 + 비교(N번): 시간복잡도 N

 

따라서, 시간 복잡도 N < NlogN로, 배열을 사용하지 않은 풀이가 더 빠른 것을 알 수 있다.

 

10818번: 최소, 최대