문제 요약
- 수열에서 원소들의 순서를 유지해 뽑은 부분수열 중, 길이가 짝수이고 인접한 쌍마다 서로 다른 두 수이면서 모든 쌍에 공통으로 포함되는 값이 존재하면 이를 “스타 수열”이라 한다.
- 가장 긴 스타 수열의 길이를 구한다. 없으면 0.
핵심 관찰
- 모든 쌍에 공통으로 포함되는 값이 꼭 1개여야 하는 건 아니다. “최소 1개 이상”이지만, 최장 길이를 만들 때는 특정 값
v를 공통 원소로 삼아도 충분하다.
- 어떤 값
v가 f번 등장하면, v를 포함하는 쌍은 최대 f개까지 만들 수 있고, 길이 상한은 2 * f.
- 따라서 각 값
v를 후보로 잡고 “v를 포함하면서 두 원소가 서로 다른” 쌍을 최대한 많이 뽑으면 된다.
알고리즘
- 각 값의 등장 빈도를 구해 내림차순으로 후보를 정렬한다. 상한
2 * freq[v]가 현재 최적해보다 작거나 같으면 더 볼 필요가 없다(프루닝).
- 주어진 배열을 한 번 스캔하며 인접한 두 값
(a[i], a[i+1])을 본다.
- 두 값이 같으면 건너뛴다.
- 둘 중 하나가
v이면 해당 쌍을 채택하고, 겹치지 않게 i를 한 칸 더 건너뛴다.
- 채택한 쌍의 개수 × 2가
v를 공통 원소로 삼은 스타 수열의 최대 길이. 모든 후보에 대해 최댓값을 갱신한다.
- 시간복잡도: 빈도 집계 O(N), 후보 정렬 O(U log U), 각 후보 스캔 O(N)인데 프루닝으로 보통 빠르다. 전체적으로 실전에서 O(N + U log U) 수준.
- 공간복잡도: O(U).
구현 (JavaScript)
const solution = (a) => {
// 빈 배열 혹은 길이 1은 스타 수열 불가
if (!a || a.length < 2) return 0;
const n = a.length;
const freq = new Map();
for (let i = 0; i < n; i++) {
const v = a[i];
freq.set(v, (freq.get(v) || 0) + 1);
}
// 빈도 내림차순 후보 정렬
const candidates = Array.from(freq.entries()).sort((x, y) => y[1] - x[1]);
let best = 0;
for (let k = 0; k < candidates.length; k++) {
const v = candidates[k][0];
const f = candidates[k][1];
// 프루닝: 최대 길이 상한은 2 * f
if (f * 2 <= best) break;
let pairs = 0;
for (let i = 0; i < n - 1; i++) {
if (a[i] === a[i + 1]) continue;
if (a[i] === v || a[i + 1] === v) {
pairs++;
i++; // 겹치지 않도록 다음 인덱스 스킵
}
}
const length = pairs * 2;
if (length > best) best = length;
}
return best;
};
구현 포인트
- 인접 두 칸만 보면서 겹치지 않게 건너뛰는 게 핵심.
shift/unshift 같은 O(N) 연산은 금지, 인덱스만 움직인다.
- 프루닝으로 불필요한 후보 탐색을 일찍 종료해 큰 입력에서도 빠르게 동작.
엣지 케이스
- 길이 < 2 → 0.
- 전부 같은 값 → 서로 다른 쌍을 만들 수 없어 0.
- 값 종류가 많아도 빈도 기반 프루닝으로 안전하게 처리.
댓글