문제 설명
N개의 원소로 구성된 배열 arr[]가 주어집니다(0 ≤ arr[i] ≤ 1000). 이 문제의 목표는 오직 Ugly Number(추한 수)로만 이루어진 부분 배열(sub-array) 중 가장 긴 것의 길이를 찾는 것입니다.
여기서 Ugly Number란 소인수(prime factor)가 2, 3, 5뿐인 수를 의미합니다.
예를 들어 이러한 수열에는 다음과 같은 수들이 포함됩니다: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15…
예시
입력 배열이 {1, 2, 7, 9, 120, 810, 374}라고 가정해 보겠습니다. 이 경우 정답은 3입니다.
그 이유는 가장 긴 Ugly Number 부분 배열이 {9, 120, 810}이기 때문입니다.
접근 방법 및 알고리즘
- unordered_set 준비: 1000 미만의 모든 Ugly Number를 미리 계산하여 집합(set)에 저장합니다.
- 배열 순회: current_max(현재 연속 길이)와 max_so_far(최대 길이) 두 변수를 사용하여 배열을 탐색합니다.
- 원소 검사: 각 원소가 집합에 존재하는지 확인합니다.
- 길이 갱신: Ugly Number를 발견하면 current_max를 1 증가시키고, max_so_far와 비교하여 더 크면 값을 갱신합니다.
- 초기화: Ugly Number가 아닌 원소를 만나는 즉시 current_max를 0으로 초기화하여 새로운 연속 구간을 시작합니다.
Ugly Number 자체를 생성하는 부분은 동적 계획법(DP) 기반의 고전적인 방식을 사용합니다. 세 개의 포인터(i2, i3, i5)가 각각 2, 3, 5의 배수 후보를 추적하고, 매 단계마다 세 후보 중 최솟값을 다음 Ugly Number로 선택하는 원리입니다.
구현 예제 (C++)
#include <bits/stdc++.h>
using namespace std;
unsigned getUglyNumbers(int n) {
int ugly[n];
int i2 = 0, i3 = 0, i5 = 0;
int next_multiple_of_2 = 2;
int next_multiple_of_3 = 3;
int next_multiple_of_5 = 5;
int next_ugly_no = 1;
ugly[0] = 1;
for (int i = 1; i < n; i++) {
next_ugly_no = min(next_multiple_of_2, min(next_multiple_of_3, next_multiple_of_5));
ugly[i] = next_ugly_no;
if (next_ugly_no == next_multiple_of_2) {
i2 = i2 + 1;
next_multiple_of_2 = ugly[i2] * 2;
}
if (next_ugly_no == next_multiple_of_3) {
i3 = i3 + 1;
next_multiple_of_3 = ugly[i3] * 3;
}
if (next_ugly_no == next_multiple_of_5) {
i5 = i5 + 1;
next_multiple_of_5 = ugly[i5] * 5;
}
}
return next_ugly_no;
}
int maxUglySubarray(int arr[], int n) {
unordered_set<int> s;
int i = 1;
while (1) {
int next_ugly_number = getUglyNumbers(i);
if (next_ugly_number > 1000)
break;
s.insert(next_ugly_number);
i++;
}
int current_max = 0, max_so_far = 0;
for (int i = 0; i < n; i++) {
if (s.find(arr[i]) == s.end())
current_max = 0;
else {
current_max++;
max_so_far = max(current_max,
max_so_far);
}
}
return max_so_far;
}
int main() {
int arr[] = {1, 2, 7, 9, 120, 810, 374};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sub-array size of consecutive ugly numbers = " << maxUglySubarray(arr, n) << endl;
return 0;
}
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.
Maximum sub-array size of consecutive ugly numbers = 3
복잡도 분석
Ugly Number 사전 생성 단계는 상수 크기(1000 미만)로 제한되므로 사실상 O(1), 배열 순회 단계는 O(N)의 시간 복잡도를 가집니다. unordered_set의 조회 평균 시간이 O(1)이므로 전체 알고리즘은 선형 시간에 동작하며 매우 효율적입니다.