C++로 절대 차이가 1 이하인 요소의 최대 개수 구하기

문제 이해

n개의 요소로 이루어진 배열이 있다고 가정해 보겠습니다. 이때 선택된 임의의 두 요소 간 절대 차이가 1보다 작거나 같도록 배열에서 선택할 수 있는 요소의 최대 개수를 구하는 것이 목표입니다.

예를 들어 배열이 [2, 2, 3, 4, 5]라고 한다면 정답은 3이며, 이때 최대 개수를 만족하는 수열은 2, 2, 3입니다.

접근 방법

절대 차이가 0 또는 1이라는 조건은 선택된 숫자들이 반드시 x 또는 x + 1 형태여야 한다는 의미입니다. 따라서 다음과 같은 아이디어로 문제를 해결할 수 있습니다.

1. 맵(map) 자료구조를 사용해 배열에 등장하는 각 숫자의 빈도(frequency)를 저장합니다.
2. 맵을 오름차순으로 순회하면서 현재 값 key에 대해 key + 1이 존재하는지 확인합니다.
3. 존재한다면 occurrence[key] + occurrence[key + 1] 값을 계산하고, 지금까지의 최댓값과 비교해 갱신합니다.

결국 인접한 두 값의 빈도 합 중 최댓값이 곧 정답이 됩니다.

예제 코드

#include <iostream>
#include <map>
using namespace std;

int maxElem(int arr[], int n) {
    map<int,int> occurrence;
    // 각 요소의 빈도 계산
    for(int i = 0; i < n; ++i){
        if(occurrence[arr[i]])
            occurrence[arr[i]] += 1;
        else
            occurrence[arr[i]] = 1;
    }
    int ans = 0, key;
    map<int,int>::iterator it = occurrence.begin();
    // 인접한 두 값의 빈도 합 중 최댓값 탐색
    while(it != occurrence.end()) {
        key = it->first;
        ++it;
        if(occurrence[key+1] != 0)
            ans = max(ans, occurrence[key] + occurrence[key+1]);
    }
    return ans;
}

int main(){
    int arr[] = {2, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Result is: " << maxElem(arr, n);
}

실행 결과

Result is: 3

코드 설명

• maxElem 함수: 먼저 map에 배열 요소별 등장 횟수를 기록합니다. map은 키를 자동으로 정렬하므로 순회 시 항상 작은 값부터 큰 값 순서로 확인할 수 있습니다.
• 순회 과정: 각 키 key에 대해 key + 1이 맵에 존재하는지 검사하고, 존재하면 두 빈도의 합으로 ans를 갱신합니다.
• main 함수: 예제 배열 {2, 2, 3, 4, 5}에서 2가 2번, 3이 1번 등장하므로 2 + 1 = 3이 결과로 출력됩니다.

시간 복잡도: O(n log n) — map에 n개의 요소를 삽입할 때 각 연산에 log 시간이 소요됩니다.
공간 복잡도: O(n) — 고유한 요소의 개수만큼 맵에 저장 공간이 필요합니다.