프로그래머스 문제 - 스타 수열

프로그래머스 스타 수열 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

어떤 수열 x의 부분 수열이란, x의 몇몇 원소들을 제거하거나 그러지 않고 남은 원소들이 원래 순서를 유지하여 얻을 수 있는 새로운 수열을 말합니다.
예를 들면 [1,3]은 [1,2,3,4,5]의 부분수열입니다. 수열에서 위치를 바꾸지 않고 2,4,5를 제거하여 만들어 낼 수 있기 때문입니다.
스타 수열은 다음과 같은 조건을 만족하는 수열을 뜻합니다.
1. x의 길이가 2 이상의 짝수입니다. (빈 수열은 허용하지 않음)
2.x의 길이를 2n이라 할 때, 다음과 같은 n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다.
3.x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1] 입니다.
즉 [1,2,1,3,4,1,1,3] -> {1,2}, {1,3}, {4,1}, {1,3}로 보았을 때 교집합의 원소가 1개 이상 포함되어 있어야 하며 둘의 원소는 같지 않아야 합니다.
주어진 수열로 제일 긴 스타수열을 만들어야 합니다.

문제 풀이

위의 조건들을 잘 보면 조건에 만족하는 둘로 되어있는 집합들의 모임인 것을 알 수 있습니다.
그러니 둘로 되어있는 집합을 최대한 많이 만들어내는 것이 중요하며 그러기 위해서는 교집합의 원소가 많은 쪽이 더 많은 집합들을 만들어 낼 수 있을 것입니다.

일단 교집합으로 수를 선택하기 위해 주어진 수열의 숫자들의 갯수를 구해줍니다.
그 후 갯수를 기준으로 내림차순으로 정렬해줍니다.

vector<int> arr(a.size()+1, 0);
vector<pair<int, int>> numCount;
//숫자들의 갯수를 저장 후 큰 순서대로 정렬
for(int n : a)
{
    arr[n]++;
}
for(int i = 0; i < arr.size(); i++)
{
    if(arr[i] != 0) numCount.push_back(make_pair(i, arr[i]));
}
sort(numCount.begin(), numCount.end(), compare);

이제 교집합으로 만들 수를 들고 주어진 수열과 앞에서부터 비교하여 스타 수열인지 확인해줍니다.
검색하는 인덱스의 수와 그 앞의 수가 같지 않으며 두 수 중 교집합으로 만들 수가 포함되어 있다면 그 수들로 스타 수열을 만들 수 있습니다.

여기서 조심해주어야 하는 부분은 제일 많은 양의 수를 교집합으로 정하고 스타 수열을 만들어도 정답이 나오지 않을 수 있습니다.
그러니 결과값과 다음 교집합으로 만들 수의 갯수와 비교하여 결과값이 적을 시 추가로 더 계산을 진행해주어야 합니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b)
{
    return a.second > b.second;
}

int solution(vector<int> a) {
    int answer = -1;
    vector<int> arr(a.size()+1, 0);
    vector<pair<int, int>> numCount;
    //숫자들의 갯수를 저장 후 큰 순서대로 정렬
    for(int n : a)
    {
        arr[n]++;
    }
    for(int i = 0; i < arr.size(); i++)
    {
        if(arr[i] != 0) numCount.push_back(make_pair(i, arr[i]));
    }
    sort(numCount.begin(), numCount.end(), compare);
    
    int maxCount = 0;
    for(int i = 0; i < numCount.size(); i++)
    {
        int result = 0;
        //나온 결과보다 더 작은 갯수를 가지면 계산할 필요X
        if(maxCount <= numCount[i].second)
        {
            for(int j = 0; j < a.size()-1; j++)
            {
                //현재 인덱스와 그 앞의 수가 다르며
                if(a[j] != a[j+1])
                {
                    //둘중 하나라도 교집합의 원소가 포함되있으면
                    if(numCount[i].first == a[j] || numCount[i].first == a[j+1])
                    {
                        result++;
                        j++;
                    }
                }
            }
        }
        maxCount = max(maxCount, result);
    }
    answer = maxCount * 2;
    
    return answer;
}

출처

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