Programmers - 보석 쇼핑

---

title: Programmers - 보석 쇼핑
date: 2022-10-13
tags:

• Algorithm

---

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

문제 요약

진열대에 있는 보석의 특정 구간을 구매하여 모든 종류의 보석을 구매하려고 한다.
가장 적게 구매할 수 있는 구간을 찾아 시작 번호와 끝 번호만 vector에 넣어 return한다.

문제 풀이

최대 100K이며, 보석의 종류의 개수 제한이 없다.
O(n^2)의 경우 최적화를 해야 하는데, 카카오의 문제이기에 O(n) 혹은 O(nlogn)을 의도한 문제라고 판단하였다.
보석을 종류별로 분류한 후, 이 분류한 것들을 순서대로 확인하는 방식으로 문제를 해결하였다.


각 보석을 종류별로 분류하며, 진열대 번호를 저장한다.
앞에서부터 조회하였기에 각 종류별 vector는 오름차순으로 정렬이 되어 있다.
각 vector의 첫 원소들을 종합하여 max, min 값이 해당 보석들을 구매할 때의 최소 구간이다.
이 방식만 이용할 경우 효율성 테스트 13, 15번에서 TLE가 발생하였다.
여기에 priority_queue를 도입하여 함수 호출 1회만으로 정답을 구할 수 있도록 변경하였다.
가장 앞에 있는 보석을 제거한 후, 해당 보석이 더 이상 없다면 이미 최적 구간을 구했기에 바로 return한다.
보석이 남아있다면 다시 priority_queue에 넣은 후, max 값을 갱신한 후 최적 구간인지 비교한다.


끝나고 다른 유저의 풀이를 확인해보니 map을 이용하여 간단하게 해결하였다.
투포인터 방식이라면 이러한 복잡한 알고리즘 없이 빠르게 해결할 수 있는 문제였다.
카카오 문제이기에 이를 실제로 겪을 수 있는 문제에 적용해보려고 하였으나, 마땅히 떠오르는 문제가 생각나지 않는다.

프로그램

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

using std :: vector ;
using std :: string ;
using std :: unordered_map ;
using std :: pair ;
using std :: max ;
using std :: priority_queue ;

struct gemInfo
{
    int iGemIndex ;
    int iStandIndex ;
} ;

struct comp
{
    bool operator () ( gemInfo & g1 , gemInfo & g2 )
    {
        return g1.iStandIndex > g2.iStandIndex ;
    }
} ;

pair < int , int > pGetFrontRange ( vector < vector < int > > & vGemPosition )
{
    int iGemSize = vGemPosition.size () ;
    int iMax = -1 ;
    priority_queue < gemInfo , vector < gemInfo > , comp > pqGem ;
    pair < int , int > pReturn ;



    for ( int i = 0 ; i < iGemSize ; ++i )
    {
        int iTemp = vGemPosition [ i ] [ 0 ] ;

        iMax = max ( iMax , iTemp ) ;
        pqGem.push ( { i , iTemp } ) ;
    }

    pReturn.first = pqGem.top ().iStandIndex ;
    pReturn.second = iMax ;

    while ( true )
    {
        // Erase old gem
        gemInfo currentGem = pqGem.top () ;
        pqGem.pop () ;
        vGemPosition [ currentGem.iGemIndex ].erase ( vGemPosition [ currentGem.iGemIndex ].begin () ) ;


        if ( vGemPosition [ currentGem.iGemIndex ].empty () )
            break ;

        pqGem.push ( { currentGem.iGemIndex , vGemPosition [ currentGem.iGemIndex ] [ 0 ] } ) ;


        // Check if better range exist
        iMax = max ( vGemPosition [ currentGem.iGemIndex ] [ 0 ] , iMax ) ;

        if ( iMax - pqGem.top ().iStandIndex < pReturn.second - pReturn.first )
        {
            pReturn.first = pqGem.top ().iStandIndex ;
            pReturn.second = iMax ;
        }
    }


    return pReturn ;
}

vector < int > solution ( vector < string > gems )
{
    int iGemSize = gems.size () ;
    int iGemCount = 0 ;
    unordered_map < string , int > umStrToIndex ;
    vector < vector < int > > vGemPosition ;



    for ( int i = 0 ; i < iGemSize ; ++i )
    {
        int iTemp = umStrToIndex [ gems [ i ] ] ;
        if ( 0 == umStrToIndex [ gems [ i ] ] )
        {
            iTemp = ++ iGemCount ;
            umStrToIndex [ gems [ i ] ] = iTemp ;

            vector < int > vTemp ;
            vGemPosition.emplace_back ( vTemp ) ;
        }
        vGemPosition [ iTemp - 1 ].emplace_back ( i + 1 ) ;
    }

    pair < int , int > pAnswer ;
    pAnswer = pGetFrontRange ( vGemPosition ) ;


    return { pAnswer.first , pAnswer.second } ;
}