문제 개요
크기가 N인 정렬되지 않은 정수 배열이 주어졌다고 가정해 봅시다. 이때 우리가 해야 할 일은 배열에 존재하는 서로 다른(중복되지 않은) 최댓값과 두 번째 최댓값을 찾는 것입니다. 배열에는 중복된 요소가 포함될 수 있으므로, 반드시 고유한 값만을 대상으로 삼아야 합니다.
입력 예시 1 −
N = 5
A[ ] = { 2, 2, 1, 3, 4 }
출력 −
4 3
설명 − 주어진 배열에서 '4'가 최댓값이고, '3'이 두 번째 최댓값임을 알 수 있습니다.
입력 예시 2 −
N = 4
A[ ] = { 1, 3, 3, 2 }
출력 −
3 2
설명 − 크기가 4인 배열에서 '3'이 가장 크고 '2'가 두 번째로 큰 값이므로, 결과로 3과 2를 반환합니다.
문제 해결 접근 방법
크기 N의 배열에는 중복 요소가 존재할 수 있습니다. 배열에서 최댓값과 두 번째 최댓값을 효율적으로 찾기 위해, 두 개의 변수를 초기화하여 각각 max(최댓값)와 second max(두 번째 최댓값)를 저장하도록 구성할 수 있습니다.
배열을 순회하는 도중 현재 요소가 기존 최댓값보다 크다면, 현재 값을 max에 저장하고 기존의 max 값은 second max로 옮깁니다.
중복 없는 고유한 값을 찾기 위해서는 현재 요소가 max와 같은지 여부도 함께 확인해야 합니다. 즉, 현재 값이 max와 같지 않으면서 second max보다 클 경우에만, 기존 second max 값을 현재 값으로 교체합니다.
배열의 크기 N을 입력받고 배열을 초기화합니다.
maxAndSecondMax(int arr[], int size) 함수는 배열과 그 크기를 입력으로 받아, 해당 배열의 최댓값과 두 번째 최댓값을 계산하여 반환합니다.
배열 요소를 순회하면서 현재 요소가 max보다 크면, 현재 값을 max에 저장하고 기존 max 값은 second max로 이동시킵니다.
그렇지 않은 경우, 현재 값이 second max보다 크면서 동시에 max와 같지 않다면 기존 second max 값을 현재 값으로 교체합니다.
모든 순회가 끝난 후 second max에 유효한 값이 저장되어 있는지 확인합니다. 초기값(INT_MIN) 그대로라면 두 번째 최댓값이 존재하지 않는 것이므로 -1로 처리합니다.
최종 결과로 max와 second max를 출력합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
void maxAndSecondMax(int *arr, int size){
int max= INT_MIN;
int s_max= INT_MIN;
for(int i=0;i<size; ++i){
if(arr[i] >max){
s_max= max;
max= arr[i];
}
else if(arr[i]> s_max && arr[i]!= max){
s_max= arr[i];
}
}
if(s_max==INT_MIN){
s_max= -1;
}
cout<<max<<" "<<s_max;
}
int main(){
int N= 6;
int A[N]= {1,3,2,5,6,3};
maxAndSecondMax(A,N);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 나타납니다.
6 5
6과 5는 배열 내 서로 다른 고유한 값으로, 각각 최댓값과 두 번째 최댓값에 해당합니다. 이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(N)이며, 추가 메모리 사용 없이 O(1) 공간 복잡도로 문제를 해결할 수 있다는 장점이 있습니다.