프로그래머스 스타 수열 JAVA 풀이 (그리디, 시간복잡도)

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/70130

---

📌 문제 개요

배열의 부분수열 중에서 특정 조건을 만족하는 “스타 수열”의 최대 길이를 구하는 문제이다.
스타 수열은 각 쌍마다 공통으로 등장하는 원소가 존재해야 하며, 각 쌍의 원소는 서로 달라야 한다.

 

 

---

📌 접근 방법

• 스타 수열은 반드시 하나의 공통 원소를 가진다.
• 따라서 모든 경우를 탐색하는 것이 아니라 특정 값 v를 기준으로 수열을 구성
• 배열을 순회하며
  • v가 포함된 쌍만 선택
  • 한 번 사용한 원소는 다시 사용하지 않도록 skip 처리

---

📌 핵심 아이디어

스타 수열 = "공통 원소 기반 수열"

각 값 v를 기준으로 최대 쌍을 만들면 된다

핵심 조건: (a[i] == v || a[i+1] == v) && a[i] != a[i+1]

 

---

📌 전체 코드

import java.util.*;

class Solution {
    public int solution(int[] a) {

        int n = a.length;
        if (n < 2) return 0;

        int[] count = new int[n];
        for (int num : a) {
            count[num]++;
        }

        int answer = 0;

        for (int v = 0; v < n; v++) {

            if (count[v] * 2 <= answer) continue;

            int pair = 0;

            for (int i = 0; i < n - 1; i++) {

                if ((a[i] == v || a[i + 1] == v) && a[i] != a[i + 1]) {
                    pair++;
                    i++;
                }
            }

            answer = Math.max(answer, pair * 2);
        }

        return answer;
    }
}

 

---

🧾 정리

• 완전탐색이 아닌 값 기준 그리디 접근
• 핵심은 “공통 원소” 개념 파악
• 시간복잡도 O(N)으로 효율성 통과 가능