[1일 1알고] 스타 수

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

프로그래머스

 

dp인척하는 그리디 문제입니다.

 

코드 자체는 완성하면 간단한데 의도를 파악하는게 어렵네요

 

스타 수열은 길이 2의 집합들이 특정 값을 공통적으로 포함하며 집합 내에서는 서로 다른 숫자를 가지는 경우입니다.

 

a의 부분 수열 중 가장 길이가 긴 스타 수열을 찾아야합니다.

{1, 1, 2, 3, 1, 4} 이렇다면 {1, 2}, {3, 1} 혹은 {1, 3}, {1, 4} 등이 답이 될 수 있습니다.

 

부분수열이 들어가며 a의 길이가 최대 50만 이기때문에 dp로 해결해야할까가 가장 먼저 떠오릅니다.

 

다만 실제로는 복잡하게 생각할 필요가 없는 문제였습니다.

---

만약 쌍이 완성되면 index를 2씩 증가시키고 아니라면 index를 1씩 증가시킨다면 기본적으로 정답에 맞는 경우를 고려할 수 있기 때문입니다.

 

또한 a의 내부 원소들의 값이 a의 길이보다 작기 때문에 코드를 구성하기도 편하게 되어있습니다.

---

#include <string>
#include <vector>
using namespace std;
int solution(std::vector<int> a) {
    int answer = -1;
    int N = a.size();
    if (N < 2)
        return 0;
    else if (N < 4)
        return 2;

    
    vector<int> cnt(N, 0);

    for (int elem : a)
    {
        ++cnt[elem];
    }

    for (int i = 0; i < N; ++i)
    {
        int target = i;
        if (cnt[i] == 0)
            continue;
        int pair_cnt = 0;

        if (cnt[i] * 2 < answer) continue;

        for (int j = 0; j < N-1;)
        {
            if ((a[j] == target && a[j + 1] != target) ||
                (a[j] != target && a[j + 1] == target))
            {
                j += 2;
                pair_cnt += 2;
            }
            else
            {
                ++j;
            }
        }
        answer = max(answer, pair_cnt);
    }

    return answer;
}