Programmers - 스타 수열

---

title: Programmers - 스타 수열
date: 2022-08-18
tags:

• Algorithm

---

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

문제 요약

수열이 주어지며, 이 수열의 순서를 유지하되 일부의 서로 다른 수 두 개를 쌍으로 묶어 집합으로 만든다.
모든 집합에 동일한 수가 들어가도록 구성할 때, 구성 가능한 최대의 집합의 개수를 return한다.

문제 풀이

총 500K의 수가 주어진다.
DFS 방식 혹은 Parametric Search, 모든 수를 이용하여 비교하는 방식은 1분이 주어져도 시간 초과가 생길 가능성이 매우 높다.
시간 내에 정답을 찾기 위해 각 수를 이용하되 개수가 많은 수를 먼저 이용한다.


각 수의 index를 vector에 저장한 뒤, 각 vector의 길이를 기준으로 정렬한다.
길이가 긴 vector부터 집합을 구성하여 최대로 구성 가능한 집합의 개수를 구한다.
이미 구한 최대 집합의 개수가 다음에 비교할 vector의 길이보다 크거나 같다면, 이후의 vector는 비교하여도 최대값은 갱신이 되지 않는다.


최대 약 304ms의 성능을 보여주었으며, 현재 알고리즘은 O(n^2)이다.
각 수를 한 번씩만 순회하며 각 수 별로 최근에 구성한 집합의 index와 최대 길이를 저장하면 O(n)의 알고리즘으로 개선할 수 있다는 것을 확인하였다.

프로그램

#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using std :: vector ;
using std :: unordered_map ;
using std :: priority_queue ;

struct numberInfo
{
    int iCount ;
    vector < int > vIndexList ;
} ;

struct comp
{
    bool operator () ( const numberInfo & n1 , const numberInfo & n2 )
    {
        return n1.iCount < n2.iCount ;
    }
} ;

int solution ( vector < int > a )
{
    int answer = 0 ;
    unordered_map < int , vector < int > > umNumberIndex ;        // < number , vector having index of number
    int iNumberSize = a.size () ;
    priority_queue < numberInfo , vector < numberInfo > , comp > pqNumber ;



    if ( iNumberSize <= 3 )
        return 0 ;

    for ( int i = 0 ; i < iNumberSize ; ++i )
    {
        umNumberIndex [ a [ i ] ].emplace_back ( i ) ;
    }
    for ( auto iter = umNumberIndex.begin () ; iter != umNumberIndex.end () ; ++ iter )
    {
        pqNumber.push ( { ( int ) ( iter -> second.size () ) , iter -> second } ) ;
    }

    while ( ! pqNumber.empty () )
    {
        numberInfo currentNumber = pqNumber.top () ;
        pqNumber.pop () ;

        if ( currentNumber.iCount << 1 <= answer )
            break ;

        int iFormerPairIndex = 0 == currentNumber.vIndexList [ 0 ] ? 1 : currentNumber.vIndexList [ 0 ] - 1 ;
        int iCount = 1 ;


        for ( int i = 1 ; i < currentNumber.iCount ; ++i )
        {
            int iCurrentNumber = currentNumber.vIndexList [ i ] ;


            if ( iFormerPairIndex == iCurrentNumber )
            {
                continue ;
            }
            else if ( ( iFormerPairIndex + 1 == iCurrentNumber ) || ( currentNumber.vIndexList [ i - 1 ] + 1 == iCurrentNumber ) )
            {
                if ( iCurrentNumber + 1 == currentNumber.vIndexList [ i + 1 ] )
                    continue ;

                iFormerPairIndex = iCurrentNumber + 1 ;

                if ( iFormerPairIndex == iNumberSize )
                    break ;
            }
            else
            {
                if ( iCurrentNumber - 1 == currentNumber.vIndexList [ i - 1 ] )
                    continue ;

                iFormerPairIndex = iCurrentNumber - 1 ;
            }


            ++ iCount ;
        }

        answer = std :: max ( answer , iCount << 1 ) ;
    }


    return answer ;
}