코딩테스트 -- 스타 수열 - (프로그래머스 / C++)

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

프로그래머스

 

문제!

---

다음과 같은 것들을 정의합니다.

• 어떤 수열 x의 부분 수열(Subsequence)이란, x의 몇몇 원소들을 제거하거나 그러지 않고 남은 원소들이 원래 순서를 유지하여 얻을 수 있는 새로운 수열을 말합니다.
  • 예를 들어, [1,3]은 [1,2,3,4,5]의 부분수열입니다. 원래 수열에서 2, 4, 5를 제거해서 얻을 수 있기 때문입니다.
• 다음과 같은 조건을 모두 만족하는 수열 x를 스타 수열이라고 정의합니다.
  • x의 길이가 2 이상의 짝수입니다. (빈 수열은 허용되지 않습니다.)
  • x의 길이를 2n이라 할 때, 다음과 같은 n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다.
  • 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} 이고, 각 집합 내의 숫자들이 서로 다르기 때문입니다.

1차원 정수 배열 a가 매개변수로 주어집니다. a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 길이를 return 하도록 solution 함수를 완성해주세요. 이때, a의 모든 부분 수열 중에서 스타 수열이 없다면, 0을 return 해주세요.

 

 

---

요약하면 주어진 배열의 수들을 가지고 부분수열을 만들껀데 다음의 조건에 맞는 가장 길이가 긴 스타수열을 구하여라!

 

1. 길이가 짝수

2. 2개씩 나누었을때 집합 간의 교집합의 원소가 1개이상

3. 2개씩 나누었으래 서로간의 값은 달라야 함

 

조건이 좀 까다로워 보이긴 하지만 

앞뒤 비교하는 것이기에 그렇게 어려워 보이진 않네요!

 

그렇다고 모든 부분수열에 대해서 조건에 해당하는지 보기에는 주어지는 배열의 길이가 500000.... 좀 많아서

 

 

일단 어떤 경우에 최대가 되는지 생각해봅시다!

조건을 가지고 추론을 해보면...

1번조건은 짝수만 되면 되기에 길이에 영향을... 끼치진 않을것 같고

3 번 조건에서도 서로 값만 ㄷ다르면 되기에 상관없을것 같습니다!

 

 

하지만 2번! 교집합은 무조건 등장해야한다는 점!

 

만약 1을 교집합으로 가진다면 모든 집합들에 1이 있어야하고  >> 길이가 길어질려면? >> 1이 많이 존재해야 합니다!

>> 그렇다면 숫자별로 갯수를 체크한뒤 제일 많이 등장한 것들을 중심으로 생각해준다면?

 

 

그럼 코드시작!

 

일단 숫자별로 몇개씩있는지 체크해줍시다.

vector <int> cnt(a.size());
    
    for(int i =0;i<a.size();i++){
        cnt[a[i]]++;
    }

 

지금까지 나온 길이와 교집합의 수(i)를 비교하여 한번 걸러줍시다!

for(int i=0;i<cnt.size();i++){
        if(cnt[i]<=answer){
            continue;
        }

 

그다음 조건에 맞는 구간을 탐색하여 길이를 구해줍시다....!

int result=0;
        
        for(int j=0; j<a.size()-1; j++){
            if((a[j] ==i or a[j+1] ==i)and a[j]!=a[j+1]){//1 , 3 번 조건!
                result++;
                j++;
            }   
        }
        answer=max(answer,result);

 

엥... 여기가 끝

 

배열길이는 문제가 되지 않았습니다...

 

그냥 조건에 맞는지 탐색하는 문제 였네요 + 길이로 한번 걸러주기(교집합을 이용한?)

 

 

ALL

#include <string>
#include <vector>
#include <algorithm>

#include <iostream>
using namespace std;

int solution(vector<int> a)
{
    int answer = 0;
    vector <int> cnt(a.size());
    
    for(int i =0;i<a.size();i++){
        cnt[a[i]]++;
    }
    
    for(int i=0;i<cnt.size();i++){
       
        if(cnt[i]<=answer){
            continue;
        }
        
        int result=0;
        
        for(int j=0; j<a.size()-1; j++){
            if((a[j] ==i or a[j+1] ==i)and a[j]!=a[j+1]){//
                result++;
                j++;
            }
            
            
        }
        
        answer=max(answer,result);
    }
    
    return answer*2;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!