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

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

프로그래머스

 

 

단순한 문제로 대충 조건만 찾아주면 되는 문제이다. 접근 방식은 수열 중에서 가장 많이 등장한 수부터 시작해서 이 수(N)를 갖고 스타 수열이 되게끔 찾게 해줬다. 이때 스타 수열에 속하지 않는 것들을 걸러주면서 진행했는데 걸러주는 조건문은 다음과 같다.

• 0번 인덱스와 1번 인덱스 값 모두 N일 때 0번 인덱스는 스타 수열 추가 X
• 맨 마지막 인덱스와 맨 마지막 전 인덱스의 값 모두 N일 때 맨 마지막 인덱스는 스타 수열 추가 X
• 끝에 위치하지 않은 인덱스와 앞과 뒤 인덱스 값 모두 N일 때 스타 수열 추가 X
• 스타수열에 추가된 인덱스를 check 표시를 남겨 check 표시에 의해 추가할 수 없으면 스타 수열에 추가 X

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <memory.h>

using namespace std;

vector<pair<int,int>> v(500000);
bool check[500000];

bool compareByValue(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.second > b.second;
}

int solution(std::vector<int> a) {
    int answer = 0;
    for(int tmp : a){
        v[tmp].first=tmp;
        v[tmp].second=v[tmp].second+1;
    }
    
    sort(v.begin(), v.end(), compareByValue);
    
    if(a.size()==1||a.size()==2 || a.size()==3){
        return 0;
    }
    for(auto i = v.begin(); i!=v.end(); i++){
        if(i->second==1){
            break;
        }else if(i->second==2){
            if((a[0]==i->first&&a[1]==i->first) || (a[a.size()-2]==i->first&&a[a.size()-1]==i->first)){
                continue;
            }
        }else if(answer>=i->second){
            break;
        }
        int nowVal=0;
        
        for(int j = 0; j<a.size(); j++){
            if(a[j]==i->first){
                if(j==0&&a[j+1]==i->first){
                    continue;
                }
                if(j==a.size()-1&&a[j-1]==i->first){
                    continue;
                }
                if(j!=0&&j!=a.size()-1&&a[j-1]==i->first&&a[j+1]==i->first){
                    continue;
                }
                if(j==0){
                    check[1]=true;
                    nowVal++;
                    continue;
                }
                if(j==a.size()-1){
                    if(check[a.size()-2]){
                        continue;
                    }
                    nowVal++;
                    continue;
                }
                if(check[j-1]){
                    if(a[j+1]==i->first)
                        continue;
                    else{
                        check[j+1]=true;
                        nowVal++;
                        continue;
                    }
                }
                if(a[j-1]==i->first){
                    check[j+1]=true;
                    nowVal++;
                    continue;
                }
                check[j-1]=true;
                nowVal++;
            }
        }
        memset(check, false, sizeof(check));
        answer = max(answer, nowVal);
    }
    return answer*2;
}