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

 

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

10818번: 최소, 최대

 

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

1차원 배열 카테고리의 첫 문제다. 그리 어려운 것은 아닌지라 쉽게 푸실 수 있을 것이다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

배열에 대해 이미 알고있다면 이 문제는 그렇게 어렵지는 않은 문제다.

 

사실 최소, 최대를 찾는다면 배열을 쓸 필요가 없기도 하다. 하지만, 배열의 첫 카테고리인만큼 배열로 먼저 접근해서 풀어보고, 그 다음 마지막으로 배열을 쓰지 않고 푸는 방식도 보여주도록 하겠다.

 

 

 

 

그러면 배열을 사용하여 어떻게 최소 최댓값을 찾느냐.. 가장 쉬운 방법은 입력받은 값들이 저장 된 배열을 '정렬'을 활용하여 푸는 방식이다.

 

예로들어 {3, 1, 2, 5, 6}  이렇게 되어있는 배열이 있다면, 오름차순으로 정렬을 하게 되면 다음과 같이 될 것이다.

{1, 2, 3, 5, 6}

 

 

이렇게 배열을 정렬하게 되면 가장 앞의 원소, 즉 인덱스 0은 최솟값이 되고, 마지막 원소인 인덱스 4는 최댓값이 된다. (참고로 당연한 말이지만 배열의 인덱스는 0부터 시작한다.)

 

그럼 sort함수를 어떻게 쓰는지가 관건이겠다.

array라는 배열에 N개의 크기를 갖고있다고 할 때, 기본적으로 다음과 같은 형태다. 

 

// sort(배열의 시작 주소, 배열의 마지막 주소)
sort(array + 0, array + N);

 

 

위 함수는 시작주소(포함) ~ 끝 주소(미포함) 범위를 '오름차순'으로 정렬해주는 형식이다.

 

보통은 N개의 크기를 갖고있는 배열에 대해 전체를 정렬하는 경우 더 간단하게 sort(array, array + N); 이런식으로 쓰긴 하지만, 만약 일정 부분만 정렬하고 싶다면 array 에 수를 더해서 시작 주소 혹은 끝 주소를 설정할 수도 있다.

 

그러면 array[0]에는 최솟값이, array[N-1] 에는 최댓값이 저장되어있을테고, 이 두 원소를 출력해주면 되는 것이다.

 

 

 

위 함수를 토대로 풀이하는 방식도 있지만, 다른 방식으로는 매 번 입력 때마다 최솟값인지 최댓값인지를 체크하는 방식도 있다. 이 풀이 방식은 코드를 보면서 설명해주도록 하겠다.

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

배열을 활용한 풀이 방식과 배열을 활용하지 않는 방식, 이렇게 두 가지를 풀이해보도록 하겠다.

 

 

1. 배열 사용 방식

2. 배열 미사용 방식

 

 

 

 

---

• 풀이

- 방법 1 : [배열 사용 방식]

 

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {

	ios_base::sync_with_stdio(0);

	int N;
	cin >> N;

	int array[1000001];

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

	sort(array, array + N);		// 0 ~ N-1 범위 정렬

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

	return 0;

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

N을 입력받아 N개의 크기를 갖는 int형 배열 array를 생성하고, sort()함수를 통해 오름차순으로 정렬한 뒤, 양 끝단에 있는 원소를 출력해주는 방식이다.

 

 

 

 

---

- 방법 2 : [배열 미사용 방식]

 

 

 

사실 이 번 문제는 배열을 굳이 사용해줄 필요는 없다.

최솟값을 갖는 변수 하나, 최댓값을 갖는 변수 하나 이렇게 두고 입력 받을 때 마다 최솟값을 갖는 변수에 해당 값과 입력받은 수 중 더 작은 값으로 갱신을 해주고, 다음으로 입력받은 수와 최댓값을 갖는 변수를 비교하여 더 큰 값을 최댓값을 갖는 변수에 저장하여 갱신해주면 되는 것이다.

 

위 방식을 사용하기 위해서는 일단 주어지는 문제에서 입력값은 -1,000,000 ~ 1,000,000 사이의 값을 갖는다고 했으므로 최솟값을 갖는 변수는 초기값으로 1,000,001 혹은 그 이상의 값을, 최댓값을 갖는 변수는 -1,000,001 혹은 그 이하의 값을 갖고 있어야한다.

 

그래야 입력을 받을 때 마다 최솟값을 갖는 변수는 최솟값을 갱신하면서 최종적으로 실제로 입력받은 케이스에 최솟값을 갖게 되고, 최댓값을 갖는 변수는 마찬가지로 최댓값을 갖게되기 때문이다.

 

만약 테스트케이스로 N은 1이고, 그 다음 입력으로-1,000,000 만 주어지게 된다면 최대 최소 모두 -1,000,000 이 되어야하며, 그 반대로 1,000,000 만 입력받을 수도 있다.

 

그러니 반드시 최댓값 변수, 최솟값 변수는 문제의 입력 범위 밖의 값으로 설정해주어야 한다.

일단 코드를 보면 이해가 가실 것이다.

 

 

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {

	ios_base::sync_with_stdio(0);

	// minValue, maxValue의 초기값
	int minValue = 1000001;
	int maxValue = -1000001;

	int N;
	cin >> N;

	int inputValue;
	for(int i = 0; i < N; i++) {
		cin >> inputValue;

		// 입력으로 들어온 값이 minValue보다 작다면 min을 inputValue로 갱신
		if (inputValue < minValue) {
			minValue = inputValue;
		}
		// 입력으로 들어온 값이 maxValue보다 크다면 max를 inputValue로 갱신
		if (inputValue > maxValue) {
			maxValue = inputValue;
		}
	}

	cout << minValue << " " << maxValue;
	return 0;

}

 

위와 같이 풀이할 수도 있다.

 

 

참고로 위 조건문 대신 algorithm 헤더에 있는 min() max() 함수로 대체해서 다음과 같이 쓸 수도 있다.

 

minValue = min(minValue, inputValue);
minValue = max(minValue, inputValue);

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 31372653  -  방법 2 : 배열 미사용 방식

채점 번호 : 31372646  -  방법 1 : 배열 사용 방식

 

 

보시다시피 배열을 사용하지 않는 방식이 시간이 좀 더 빠른 것을 볼 수 있다.

 

이는 각 과정을 생각해보면 다음과 같다.

배열 사용 방식의 경우

배열을 입력 받는 과정 : 총 N번

배열을 정렬하는 과정 : 약 NlogN  (C++의 sort의 경우 intro sort로 시간복잡도가 NlogN이다.)

 

배열을 사용하지 않는 방식의 경우

배열의 입력과 동시에 비교과정 : 총 N번

 

즉, 프로세스상 배열을 사용하지 않는 방식이 훨씬 적다. (물론 조건문도 고려를 해야하겠지만, 이는 오버헤드에 포함되는 부분이라 크게 고려해줄 필요는 없다)

 

 

---

• 정리

 

이 번 문제는 배열을 다뤄보셨다면 크게 어려운 부분은 없었을 것이다.

필자가 배열을 사용하지 않는 코드를 보여준 이유는 배열의 카테고리에 있다고 항상 그 방식으로만 풀이 할 필요는 없다는 것이다. (물론 배열로 풀이를 할 수 있다는 전제하에..)

 

다양한 방식으로 고민을 해보고 더 좋은 풀이가 있다면 그 방식으로 풀이해보는 것이 앞으로의 알고리즘 문제를 푸는데 많은 도움이 될 것이다.

 

혹여 어렵거나 이해가 가지 않는 부분이 있다면 언제든 댓글을 남겨주시기 바란다. 최대한 빠르게 답변드릴 수 있도록 노력하겠다.