문제 개요
서로 다른 정수들로 이루어진 리스트 nums가 주어졌을 때, nums에 포함된 숫자를 최대 하나만 담을 수 있는 가장 큰 구간(양 끝점 포함) [start, end]의 크기를 구하는 것이 이번 문제의 목표입니다.
예를 들어 입력이 nums = [10, 6, 20]이라면 출력은 99990이 됩니다. 가장 큰 구간은 [11, 100000]이며, 이 구간에는 20 하나만 포함되기 때문입니다.
해결 접근 방법
이 문제는 배열을 정렬한 뒤, 각 숫자를 기준으로 인접한 숫자들 사이의 빈 공간(간격)을 계산하는 방식으로 해결할 수 있습니다. 탐색 가능한 전체 범위는 1부터 100000까지라고 가정합니다.
구체적인 풀이 단계는 다음과 같습니다.
- 결괏값을 저장할 변수 ret을 음의 무한대(-inf)로 초기화합니다.
- 탐색 범위의 끝을 나타내는 end를 100000으로 설정합니다.
- 이전 숫자를 저장할 변수 prev를 1로 초기화합니다.
- 배열 nums를 오름차순으로 정렬합니다.
- n에 배열의 크기를 저장합니다.
- i를 0부터 배열 크기까지 1씩 증가시키며 반복합니다.
- i + 1 < n이면 high를 nums[i + 1] - 1로 설정하고, 그렇지 않으면 high를 end로 설정합니다.
- i - 1 >= 0이면 low를 prev + 1로 설정하고, 그렇지 않으면 low를 prev로 설정합니다.
- prev를 nums[i]로 갱신합니다.
- ret을 high - low + 1과 ret 중 더 큰 값으로 갱신합니다.
- 반복이 끝나면 ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int> &nums) {
int ret = INT_MIN;
int end = 100000;
int prev = 1;
sort(nums.begin(), nums.end());
int n = nums.size();
int low, high;
for (int i = 0; i < nums.size(); i++) {
if (i + 1 < n) {
high = nums[i + 1] - 1;
} else
high = end;
if (i - 1 >= 0) {
low = prev + 1;
} else
low = prev;
prev = nums[i];
ret = max(high - low + 1, ret);
}
return ret;
}
};
main() {
Solution ob;
vector<int> v = {10, 6, 20};
cout << (ob.solve(v));
}
입력
{10, 6, 20}출력
99990
동작 원리 상세 설명
입력 [10, 6, 20]을 정렬하면 [6, 10, 20]이 됩니다. 각 숫자를 기준으로 후보 구간을 계산해 보면 다음과 같습니다.
- 첫 번째 숫자 6: 구간 [1, 9] → 크기 9
- 두 번째 숫자 10: 구간 [7, 19] → 크기 13
- 세 번째 숫자 20: 구간 [11, 100000] → 크기 99990
각 구간에는 해당 숫자 하나만 포함되므로 조건을 만족하며, 이 중 가장 큰 값인 99990이 최종 결과로 반환됩니다.
복잡도 분석
배열 정렬에 O(n log n)의 시간이 소요되고, 이후의 간격 계산은 선형 시간 O(n)에 처리되므로 전체 시간 복잡도는 O(n log n)입니다. 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다.