프로그래머스 Level 3 스타수열

스타수열 (프로그래머스 Level 3)

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

처음에는 이전처럼 dp나 ‘부분합’에 관련된 문제라고 생각하였으나
문제의 조건을 보며 다시 생각을 해보았는데

1. 스타 수열은 ‘짝수’이다
   
2. 스타 수열의 각 2n 집합의 요소는 서로 같지 않다
   
3. 스타 수열의 각 2n 집합은 하나 이상의 교집합을 갖는다
   

이 때, dp를 통해 ‘이전에 구한 계산’을 재활용할 방법이 마땅치 않기에
이 문제가 dp가 아니라고 판단하였다
(ex : 2를 교집합으로 갖는 ‘스타 수열’을
3을 기준으로 교집합을 갖는 ‘스타 수열’을 만들때 써먹을 수 있을까?)

교집합으로 공통된 수를 사용해야 하기에
‘가장 많이 등장하는 수’를 기반으로 2개씩 세어주는 방법을 사용하였다
(실제로 이 방식으로 풀 수 있었으므로 그리디 라 볼 수도 있겠다)
다만 유의할 점은
‘연속되어 등장하는 경우’에 대해서는 예외처리를 해주었다

ex) ‘1 1 1 1 1 2 3 2 4’ 일 때
1이 가장 많이 등장하지만 실제로 1로 만들 수 있는 ‘스타수열’의 길이는
2밖에 되지 않는다
하지만 2로 잡게 되는 경우는 2 3 2 4 로 4개가 된다

그렇기에 연속되어 등장하는 경우에 대하여 예외처리를 해주었다
위의 경우는 1이 ‘시작점’에 존재하기에 ‘1’개로 처리하고
4, 1, 1, 1, 1, 1, 3,2, 5 ->4
이 경우에는 ‘중간’에 끼어있으므로 2개로 세어주었다

이렇게 ‘가장 많이 등장하는 수’를 구하고
2개씩 세어, 해당 수가 포함되어 있는지를 세어준 후, 2를 곱하여 풀었다

Code

#include <string>
#include <vector>
#include<unordered_map>

using namespace std;

int solution(vector<int> a) {
    int answer = 0;

    unordered_map<int, int> nc;
    for (int i = 0; i < a.size(); i++)
    {
        int value = a[i];
        int count = 0;
        int startI = i;

        if (i < a.size() - 1 && value == a[i + 1])
        {
            for (int j = i + 1; j < a.size(); j++)
            {
                if (value == a[j])
                {
                    count++;
                }
                else
                {
                    break;
                }
            }

            if (count > 2)
                i += count;
        }

        if (startI != 0 && i != a.size() - 1 && count > 1)
        {
            nc[value] = nc[value] + 2;
        }
        else
        {
            nc[value] = nc[value] + 1;
        }
        
    }

    // nc에서 가장 개수 많은 수를 기준으로 벡터를 돌며 찾기

    int c = 0;
    int bestNums = 0;
    for (auto n : nc)
    {
        if (n.second > c)
        {
            c = n.second;
            bestNums = n.first;
        }
    }

    // bestNums를 기준으로 찾음
    for (int i = 0; i < a.size() - 1;i++) // i++ 등은 내부에서 해줄 예정이다
    {
        int value = a[i];
        int nextValue = a[i + 1];

        // 일단 두 수가 같다면 다음으로 넘긴다
        if (value == nextValue)
        {
            continue;
        }

        // 두 수는 같지 않으며,
        // 두 수 중 하나는 많은 수이다
        if (value == bestNums ||
            nextValue == bestNums)
        {
            answer++;
            i++;
        }
    }

    answer *= 2;
    return answer;
}