[백준] 2562번 : 최댓값 - [C++]

 

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

2562번: 최댓값

 

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

그리 어려운 문제는 아니다. 아마 많은 분들은 쉽게 풀었을 것 같다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

이 문제 자체는 어렵지 않다. 

 

총 9개의 서로 다른 자연수가 주어지면, 주어진 수에서 최댓값과 그 최댓값이 몇 번째로 주어졌는지를 출력하면 되는 문제다.

 

 

다만, 유의해야 할 점이라면 배열을 정렬을 시켜버리면 안된다.

 

우리가 출력해야 하는 건, 최댓값과 최댓값이 몇 번째로 입력 받았는가다. 즉, 입력 받은 순서에서 몇 번째냐라는 것이다. 만약 배열을 정렬을 하게 되면, 입력 받은대로의 순서를 유지할 수가 없다. 

(그럼에도 정렬을 사용하고자 할 경우에는 pair 클래스를 사용하는 것도 하나의 방식일 순 있긴 하다.)

 

풀이 방법이야 여러가지가 있는데, 배열을 쓰는 방법과, 쓰지 않고도 모두 풀이 할 수 있다.

 

일단 가장 기본적인 방식으로 배열을 쓰자면 풀이 자체는 간단하다.

배열에 값을 모조리 입력 받은 뒤, 배열 앞부터 하나씩 비교해나가면서 가장 큰 값을 찾는 방식이다.

 

이해하기 쉽게 코드로 보자면 다음과 같다.

 

// 배열 입력
int num[9];
for (int i = 0; i < 9; i++) {
	cin >> num[i];
}

int maxValue = -1;	// 최댓값을 갖고있을 변수 
int maxValueIndex;	// 최댓값의 위치를 갖고있을 변수
for (int i = 0; i < 9; i++) {

	// 이전값들 중 최댓값보다 i번째 값이 더 크다면 최댓값과 그 인덱스를 갱신
	if (num[i] > maxValue) {
		maxValue = num[i];
		maxValueIndex = i;
	}
}

// maxValue와 maxValueIndex+1 을 출력하면 됨

 

 

위와 같이 입력받은 배열에 대해 순회하면서 현재 값과 maxValue를 비교하면서 풀이하면 된다.

 

 

 

 

 

하지만, 생각해보자. 우리가 배열을 입력하는 과정과 순회하면서 최댓값을 찾는 과정은 동일하게 이루어진다. 그러면 다음과 같이 생각할 수 있다.

 

굳이 배열에 입력하지 말고 매 입력값이 주어질 때 마다 최댓값을 비교하면 안되는가?

 

즉, 두 번의 순회과정 필요없이 입력과 최댓값 탐색 과정을 하나로 합치는 것이다.

 

int maxValue = -1;	// 최댓값을 갖고있을 변수 
int maxValueIndex;	// 최댓값의 위치를 갖고있을 변수
int num;			// 입력받는 변수
for (int i = 0; i < 9; i++) {

	cin >> num;		// 입력받기

	// 이전값들 중 최댓값보다 현재 num값이 더 크다면 최댓값과 인덱스를 현재 i로를 갱신
	if (num > maxValue) {
		maxValue = num;
		maxValueIndex = i;
	}
}

// maxValue와 maxValueIndex+1 을 출력하면 됨

 

위와같이 더욱 간결하게 짤 수도 있다.

 

 

이를 토대로 이제 출력과 몇 가지 소스만 만들어주면 된다.

 

 

 

 

 

 

 

 

---

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

 

 

 

이 번 문제 또한 여타 다를바 없이 기본적인 입출력과 빠른 입출력을 비교하고자 한다. 다만, 그 전에 위에서 설명한 두 방법에 대해 테스트를 먼저 기본입출력에 대해 풀이해보고, 그 다음 두 번째 방식에 대해 입출력을 변경하여 풀이할 것이다.

즉, 아래와 같이 3가지 풀이 방식을 보여주고자 한다.

 

 

 

1. 알고리즘 1 (배열 사용) + 기본 입출력

2. 알고리즘 2 (배열 X) + 기본 입출력

3. 알고리즘 2 (배열 X) + 향상 된 입출력

 

 

 

 

---

• 풀이

- 방법 1 : [알고리즘 1 (배열 사용) + 기본 입출력]

 

#include <iostream>

using namespace std;

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

	// 배열 입력
	int num[9];
	for (int i = 0; i < 9; i++) {
		cin >> num[i];
	}

	int maxValue = -1;	// 최댓값을 갖고있을 변수 
	int maxValueIndex;	// 최댓값의 위치를 갖고있을 변수
	for (int i = 0; i < 9; i++) {

		// 이전값들 중 최댓값보다 i번째 값이 더 크다면 최댓값과 그 인덱스를 갱신
		if (num[i] > maxValue) {
			maxValue = num[i];
			maxValueIndex = i;
		}
	}
	cout << maxValue << "\n";
	/*
	 * 배열의 인덱스는 0부터 시작한다.
	 * 그렇기 떄문에 실제 입력받은 수는 인덱스 + 1 인
	 * 값이 입력받은 순서가 된다.
	 */
	cout << maxValueIndex + 1;
	return 0;
}

 

 

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

알고리즘도 그대로 갖고온 것이라 이해하는데 문제는 없을 것이다.

 

 

 

---

- 방법 2 : [알고리즘 2 (배열 X) + 기본 입출력]

 

 

 

 

배열을 사용하지 않고 풀이하는 방식이다.

 

 

#include <iostream>

using namespace std;

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


	int maxValue = -1;	// 최댓값을 갖고있을 변수 
	int maxValueIndex;	// 최댓값의 위치를 갖고있을 변수
	int num;			// 입력받을 변수
	for (int i = 0; i < 9; i++) {
		cin >> num;
		// 이전값들 중 최댓값보다 num 값이 더 크다면 최댓값과 그 인덱스를 갱신
		if (num > maxValue) {
			maxValue = num;
			maxValueIndex = i;
		}
	}
	cout << maxValue << "\n";
	/*
	 * 입력과 다르게 반복문에서는 0부터 시작한다.
	 * 그렇기 떄문에 실제 입력받은 수는 i + 1 인
	 * 값이 입력받은 순서가 된다.
	 */
	cout << maxValueIndex + 1;
	return 0;
}

 

 

 

 

 

 

 

---

- 방법 3 : [알고리즘 2 (배열 X) + 향상 된 입출력]

 

 

 

입력 방법을 기존의 입출력에서 stdio 와의 싱크를 끊어주어 더욱 시간을 단축시키는 방식으로 변경한 방식이다.

다만, 이 번 문제의 경우에는 입력과 출력량이 모두 다 적기 때문에 큰 의미는 있을지는 모르겠다..

 

 

#include <iostream>

using namespace std;

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

	ios_base::sync_with_stdio(false);
	cin.tie(0);


	int maxValue = -1;	// 최댓값을 갖고있을 변수 
	int maxValueIndex;	// 최댓값의 위치를 갖고있을 변수
	int num;			// 입력받을 변수
	for (int i = 0; i < 9; i++) {
		cin >> num;
		// 이전값들 중 최댓값보다 num 값이 더 크다면 최댓값과 그 인덱스를 갱신
		if (num > maxValue) {
			maxValue = num;
			maxValueIndex = i;
		}
	}
	cout << maxValue << "\n";
	/*
	 * 입력과 다르게 반복문에서는 0부터 시작한다.
	 * 그렇기 떄문에 실제 입력받은 수는 i + 1 인
	 * 값이 입력받은 순서가 된다.
	 */
	cout << maxValueIndex + 1;
	return 0;
}

 

 

 

크게 어려울 것은 없을 것이다.

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 32316682  -  방법 3 : 알고리즘 2 (배열 X) + 향상 된 입출력

채점 번호 : 32316672  -  방법 2 : 알고리즘 2 (배열 X) + 기본 입출력

채점 번호 : 32316657  -  방법 1 :  알고리즘 1 (배열 사용) + 기본 입출력

 

 

 

이 번 문제의 경우 입출력 데이터가 워낙 적어서 모두 0ms로 나오는 것으로 보인다.

 

 

 

 

---

• 정리

 

이 번 문제 또한 어려운 점은 없었을 것이다.

그럼에도 정답률이 생각보다 낮은 이유가 아마 정렬을 한 뒤에 정렬 된 배열에 대해 최댓값과 최댓값의 인덱스를 출력했기에 틀린 것이 아닐까.. 조심스레 예측해본다.