[프로그래머스/Level 3] 스타 수열 (C++)

programmers.co.kr/learn/courses/30/lessons/70130

코딩테스트 연습 - 스타 수열

 

1. map을 통해 원소들의 빈도 수를 구하기
2. map의 key를 교집합으로 설정하고, 이때 만들 수 있는 최대 스타 수열의 길이는 value(빈도 수) * 2
3. a의 배열의 a[i], a[i + 1] 값을 비교하고, 이 값들이 key와 같은지 비교하며 조건을 맞추기
4. 조건을 통과하면 현재 스타 수열의 길이는 2씩 갱신하고, 다음 비교를 위해 i++ 처리
5. 현재 key를 교집합으로 스타 수열이 길이를 구했으면 최대값을 갱신, 위를 계속 반복하기

 

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int solution(vector<int> a) {
    int answer = 0;
    unordered_map<int, int> um;
    
    for(int i = 0; i < a.size(); i++) {
        um[a[i]]++;
    }
    
    for(auto it : um) {
        if(it.second * 2 <= answer) continue;
        int tmp = 0;
        for(int i = 0; i < a.size() - 1; i++) {
            if(a[i] == a[i + 1]) continue;
            if(a[i] != it.first && a[i + 1] != it.first) continue;
            tmp += 2;
            i++;
        }
        answer = max(answer, tmp);
    }
    
    return answer;
}