[BOJ] 2562번 - 최댓값

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

2562번: 최댓값

문제

9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오.

예를 들어, 서로 다른 9개의 자연수

3, 29, 38, 12, 57, 74, 40, 85, 61

이 주어지면, 이들 중 최댓값은 85이고, 이 값은 8번째 수이다.

입력

첫째 줄부터 아홉 번째 줄까지 한 줄에 하나의 자연수가 주어진다. 주어지는 자연수는 100 보다 작다.

출력

첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 몇 번째 수인지를 출력한다.

제한

시간 제한 : 1초 / 메모리 제한 : 128MB

---

1. 어떻게 풀까?

두 가지 방법으로 풀 수 있다. STL을 이용하는 방법과 STL을 이용하지 않는 방법.

1-1) STL을 이용하지 않고 풀면

먼저 STL을 이용하지 않고 풀면 다음과 같은 논리로 풀 수 있다.

1. i번째 수를 입력 받은 다음, 현재 저장되어 있는 최댓값과 입력받은 값을 비교한다.
2. 만약 입력받은 값이 크다면 현재 저장되어 있는 최댓값을 입력받은 값으로 바꾸고, 그 순서를 따로 저장한다.

1->2번의 과정을 9번 반복하면 최댓값과 최댓값의 위치를 구할 수 있다. 이를 구현하면 다음과 같다.

2-1) 최종 코드 1

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int temp;
    int max = 0;
    int idx;
 
    for (int i = 1; i <= 9; i++){
        cin >> temp;
        if (temp > max) {
            max = temp;
            idx = i;
        }
    }
 
    cout << max << '\n' << idx;
 
    return 0;
}

 

1-2) STL을 이용하고 풀면 (max_element)

C++의 STL중 헤더 <algorithm.h>에는 max_element() 라는 함수가 존재한다.

간략하게 설명하자면 첫 번째 인자로 배열의 처음 포인터를, 두 번 인자로 배열의 끝 포인터를 입력 받아 (iterator의 개념과 관련 일단 이렇게 설명하고 넘어가자) 최댓값이 존재하는 포인터를 반환하는 함수이다. (세 번째 인자는 어떤 기준으로 최댓값을 정할 건지 정해줄 수 있는 인자이지만, 지금은 필요가 없다.)

 

int.형 vector를 만든 이후, 9개의 수를 vector안에 모두 저장한다.

 

iterator type 변수 it에 최댓값의 포인터를 저장하고, 포인터의 참조 연산자(*)를 이용하여 최댓값을 먼저 출력한다.

이후 it에 배열의 처음 포인터와 차이에 1을 더한 만큼이 최댓값이 몇 번째인지 나타내주는 수이다. (0번째 부터가 아닌 1번째부터 시작하니까!)

이를 구현하여 작성하면 다음과 같이 작성할 수 있다.

2-2) 최종 코드 2

#include <bits/stdc++.h>
using namespace std;
 
vector<int> nums;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 9; i++) {
        int temp; cin >> temp;
        nums.push_back(temp);
    }
    
    auto it = max_element(nums.begin(), nums.end());
    cout << *it << "\n" << it - nums.begin()+1;
 
    return 0;
}

 

 

PS) 1번째 방법과 2번째 방법 모두 시간복잡도 O(n) 내에 해결할 수 있다.