문제 개요
음수가 아닌 정수로만 이루어진 배열 nums가 주어졌다고 가정해 봅시다. 여기서 말하는 배열의 차수(degree)란, 배열 안에서 가장 많이 등장하는 요소의 빈도수, 즉 최대 빈도를 의미합니다. 우리가 구해야 할 것은 이 배열과 동일한 차수를 가지면서 길이가 가장 짧은 연속(contiguous) 부분 배열의 길이입니다.
예를 들어 입력 배열이 [1, 2, 2, 3, 1]이라면 결과는 2가 됩니다. 이 배열에서는 1과 2가 각각 두 번씩 등장하므로 배열의 차수는 2입니다. 동일한 차수를 가지는 부분 배열로는 [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]가 있으며, 이 중 가장 짧은 길이는 2입니다. 따라서 정답은 2가 됩니다.
해결 접근 방법
이 문제는 크게 두 단계로 나누어 생각할 수 있습니다. 먼저 전체 배열을 한 번 순회하며 각 숫자의 빈도를 세어 최대 빈도(차수)를 구하고, 이후 슬라이딩 윈도우 방식으로 조건을 만족하는 가장 짧은 구간을 찾습니다. 구체적인 단계는 다음과 같습니다.
- 크기가 50000인 배열 freq를 선언하고 모든 값을 0으로 초기화합니다.
- max_를 0으로 설정합니다.
- nums의 각 요소 n에 대해 다음을 수행합니다.
- freq[n] 값을 1 증가시킵니다.
- max_를 max_와 freq[n] 중 더 큰 값으로 갱신합니다.
- freq 배열의 모든 값을 다시 0으로 되돌립니다.
- min_을 nums의 크기로 초기화합니다.
- i := 0, j := -1, size := nums의 크기로 설정한 뒤, j < size인 동안 다음을 반복합니다.
- j >= 0이고 freq[nums[j]]가 max_와 같다면, min_을 min_과 (j - i + 1) 중 작은 값으로 갱신하고, freq[nums[i]]를 1 감소시킨 후 i를 1 증가시킵니다.
- 그렇지 않고 j < size - 1이라면, j를 1 증가시키고 freq[nums[j]]를 1 증가시킵니다.
- 위 어느 조건에도 해당하지 않으면 반복문을 종료합니다.
- 최종적으로 min_을 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
vector<int> freq(50000, 0);
int max_ = 0;
for (const int n : nums)
max_ = max(max_, ++freq[n]);
fill(freq.begin(), freq.end(), 0);
int min_ = nums.size();
for (int i = 0, j = -1, size = nums.size(); j < size;) {
if (j >= 0 && freq[nums[j]] == max_)
min_ = min(min_, j - i + 1), --freq[nums[i++]];
else if (j < size - 1)
++freq[nums[++j]];
else
break;
}
return min_;
}
};
main(){
Solution ob;
vector<int> v = {1, 2, 2, 3, 1};
cout << (ob.findShortestSubArray(v));
}실행 결과 확인
입력
{1, 2, 2, 3, 1}출력
2
알고리즘 동작 원리
첫 번째 순회에서는 각 숫자의 등장 횟수를 세어 배열의 차수(max_)를 구합니다. 두 번째 단계에서는 윈도우의 오른쪽 끝(j)을 한 칸씩 확장하며 빈도를 누적하다가, 현재 윈도우 내 어떤 숫자의 빈도가 max_에 도달하면 왼쪽 끝(i)을 줄여 나가면서 최소 길이를 갱신합니다. 이러한 슬라이딩 윈도우 기법 덕분에 전체 배열을 두 번만 순회하여 O(n) 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다.