C++로 배열의 세 번째 최댓값 찾기 – O(n) 선형 시간 풀이

비어 있지 않은 정수 배열이 주어졌을 때, 이 배열에서 세 번째로 큰 수(third maximum number)를 찾는 문제입니다. 만약 세 번째 최댓값이 존재하지 않는다면 배열의 최댓값을 대신 반환해야 합니다.

이 문제의 핵심 조건은 선형 시간 복잡도 O(n)으로 해결해야 한다는 점입니다. 즉, 배열을 정렬하는 방식(O(n log n))은 사용할 수 없으며, 배열을 한 번만 순회하면서 답을 구해야 합니다.

문제 이해하기

예를 들어 입력 배열이 [5, 3, 8, 9, 1, 4, 6, 2]라고 가정해 보겠습니다. 이 배열을 내림차순으로 정렬하면 9, 8, 6, 5, ... 순서가 되므로, 세 번째로 큰 수는 6이 됩니다.

접근 방법

배열을 순회하면서 상위 세 개의 값(최댓값, 두 번째 값, 세 번째 값)을 동시에 추적하는 전략을 사용합니다. 각 단계는 다음과 같습니다.

• 세 개의 포인터 변수 a, b, c를 NULL로 초기화합니다. 각각 최댓값, 두 번째 최댓값, 세 번째 최댓값을 가리킵니다.
• 배열의 모든 요소를 순회하면서 다음 규칙을 적용합니다.
  • 현재 요소가 a보다 크거나 같으면: 기존의 a는 b로, b는 c로 밀려나고, 현재 요소가 새로운 a가 됩니다.
  • 그렇지 않고 현재 요소가 b보다 크거나 같으면: 기존의 b는 c로 밀려나고, 현재 요소가 새로운 b가 됩니다.
  • 그렇지 않고 현재 요소가 c보다 크거나 같으면: 현재 요소가 새로운 c가 됩니다.
• 순회가 끝난 후 c가 NULL이라면 세 번째 최댓값이 존재하지 않는 것이므로 a(최댓값)를 반환하고, 그렇지 않으면 c의 값을 반환합니다.

이 방식은 배열을 딱 한 번만 순회하므로 시간 복잡도는 O(n), 추가로 사용하는 공간은 포인터 세 개뿐이므로 공간 복잡도는 O(1)입니다.

C++ 구현 코드

아래는 위 알고리즘을 실제로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int thirdMax(vector<int>& nums) {
      int *a, *b, *c;
      a = b = c = NULL;
      for (int i = 0; i < nums.size(); ++i) {
         if (!a || nums[i] >= *a) {
            if (a && nums[i] > *a) {
               c = b;
               b = a;
            }
            a = &nums[i];
         }
         else if (!b || nums[i] >= *b) {
            if (b && nums[i] > *b) {
               c = b;
            }
            b = &nums[i];
         }
         else if (!c || nums[i] >= *c) {
            c = &nums[i];
         }
      }
      return !c ? *a : *c;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,3,8,9,1,4,6,2};
   cout << (ob.thirdMax(v));
}

실행 결과 확인

입력

{5,3,8,9,1,4,6,2}

출력

6

마무리

이 풀이의 장점은 정렬 없이 단일 패스(single pass)로 해결된다는 점입니다. 다만 중복 값 처리에 유의해야 하는데, 문제에 따라 중복을 제외한 세 번째 최댓값을 구해야 할 경우에는 >= 비교를 >로 바꾸고 중복 여부를 함께 검사하도록 로직을 수정하면 됩니다. 포인터 대신 long long 타입의 세 변수와 LLONG_MIN 센티넬 값을 사용하면 더 직관적으로 구현할 수도 있습니다.