본문 바로가기
Algorithm/프로그래머스

[프로그래머스/C++] 스타 수열

by code_pie 2024. 1. 31.

 

 
 
 

 

풀이

 

[문제 풀이]

 

쉽게 말해 스타 수열이란 짝수 크기의 수열을 순서대로 2개씩 나누었을 때, 2개씩 나눈 집합에 전부 같은 숫자가 하나씩은 있어야 된다. (이때, 2개씩 나누었을 경우 같은 숫자가 2개 들어가 있으면 안된다)

 

이때 스타 수열의 크기가 가장 길 경우를 찾는 문제이므로 기본적으로 어떤 숫자가 가장 많은지 파악하는게 중요하다.

 

그래서 숫자의 개수를 센 다음 개수를 기준으로 정렬해서 어떤 숫자가 가장 많은지 파악해 정렬했다.

ex)1: 2개, 3: 1개, 1: 1개

 

여기서 max값을 찾는게 아니라 정렬을 하는 이유는 숫자가 연속적으로 붙어있다면 스타 수열의 크기는 줄어들기 때문이다.

ex) [0, 3, 0, 0] -> [0,3] 만 가능하다.

 

이후 가장 많은 개수를 가진 숫자부터 만들 수 있는 스타 배열의 크기를 계산하면 된다.

ex) A, B, C 순으로 숫자가 많다면 A가 공통으로 들어있는 스타 수열의 크기 계산, B가 공통으로 들어있는 스타 수열의 크기 계산, ...

 

이때, 모든 숫자로 스타수열을 만들 필요는 없다.

 

현재 숫자를 기준으로 만들 수 있는 스타수열의 이론적인 크기가 만들어진 스타수열의 최대 사이즈 보다 작다면 바로 return하면 된다. (내림차순으로 정렬을 해서 계산했기 때문)

 

만약 이론적으로 만들 수 있는 스타수열이 더 크다면, 실제로 만들어서 검사를 하고 값을 저장하면 된다.

 

[아이디어 정리]

  1. 숫자의 개수를 세 내림차순으로 정렬을 한다.
  2. 내림차순으로 정렬된 숫자로 스타 수열을 만들어 크기를 저장한다.
  3. 현재 숫자로 만들 수 있는 스타수열의 크기가 저장된 스타수열의 크기보다 작으면, 저장된 스타수열의 크기를 return한다.
  4. 만약 현재 숫자로 만들 수 있는 스타수열의 크기가 저장된 스타수열의 크기보다 크다면, 실제로 만들어보고 크기를 비교해 저장된 스타수열의 크기를 갱신한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int>> numVec;
vector<int>realA;
bool cmp(pair<int,int>a,pair<int,int>b)
{
    return a.first>b.first;
}

int Calc(int num)
{
    bool flagN=false,flagO=false; // 있는지 없는지
    int returnSize=0;
    for (int i=0; i<realA.size(); i++)
    {
        if (realA[i]==num)
        {
            flagN=true;
        }
        else
        {
            flagO=true;
        }
        if (flagN&&flagO)
        {
            returnSize+=2;
            flagN=false,flagO=false;
        }
    }
    return returnSize;
}

int solution(vector<int> a) {
    int answer = -1;
    realA=a;
    numVec=vector<pair<int,int>>(a.size(),make_pair(0,0));
    for (int i=0; i<a.size(); i++)
    {
        numVec[a[i]].first+=1;
        numVec[a[i]].second=a[i];
    }    
    sort(numVec.begin(),numVec.end(),cmp);
    int maxSize=0;    
    for (int i=0; i<numVec.size(); i++)
    {
        maxSize=max(maxSize,Calc(numVec[i].second));
        if (maxSize>=numVec[i].first*2)
        {
            return maxSize;
        }
    }
    return maxSize;
}

 


 
 

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형