풀이
[문제 풀이]
쉽게 말해 스타 수열이란 짝수 크기의 수열을 순서대로 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하면 된다. (내림차순으로 정렬을 해서 계산했기 때문)
만약 이론적으로 만들 수 있는 스타수열이 더 크다면, 실제로 만들어서 검사를 하고 값을 저장하면 된다.
[아이디어 정리]
- 숫자의 개수를 세 내림차순으로 정렬을 한다.
- 내림차순으로 정렬된 숫자로 스타 수열을 만들어 크기를 저장한다.
- 현재 숫자로 만들 수 있는 스타수열의 크기가 저장된 스타수열의 크기보다 작으면, 저장된 스타수열의 크기를 return한다.
- 만약 현재 숫자로 만들 수 있는 스타수열의 크기가 저장된 스타수열의 크기보다 크다면, 실제로 만들어보고 크기를 비교해 저장된 스타수열의 크기를 갱신한다.
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;
}
다른 사람들의 풀이를 보니 처음부터 스타수열을 만들 수 있는지 count를 세면서 푼 풀이들이 보였다.
나는 먼저 갯수를 세고 그 뒤에 스타 수열이 가능한지 풀어서 처음부터 검사하는게 더 나았을 것 같다.
풀면서 이게 맞나? 싶었는데 맞았다;; 좀 더 깔끔한 방법이 있을줄 알았는데....
반응형
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스/C++] 가장 긴 팰린드롬 (feat. Manacher's Algorithm) (0) | 2024.02.01 |
---|---|
[프로그래머스/C++] 카운트 다운 (0) | 2024.01.31 |
[프로그래머스/C++] 파괴되지 않은 건물 (2022 KAKAO BLIND RECRUITMENT) (0) | 2024.01.29 |
[프로그래머스/C++] 징검다리 건너기 (2019 카카오 개발자 겨울 인턴십) (0) | 2024.01.29 |
[프로그래머스/C++] 도둑질 (0) | 2024.01.28 |