스타 수열 (Java)

스타 수열이 되기위함의 가장 중요한 조건은 어떠한 부분 수열을 앞에서 부터 2개씩 묶었을때에 교집합 원소가 한개이상있어야하고 첫번쨰와 두번째 원소는 달라야 한다는 점이다.

처음으로 생각한 방법은 500000크기의 배열을 만들어주고 0~500000미만의 원소들이 공통으로 들어갔을때에 최대 길이를 저장하는 방법을 생각했다.
예를 들어서,
[5,2,3,3,5,3] 가 주어졌다면 5로 이루어진 스타배열의 총 길이는 4이기때문에 arr[5]=4, 3으로 이루어진 스타배열의 총 길이는 4로 arr[3]=4, arr[2]=2 이렇게 주어진 모든 원소로 이루어진 배열의 최대길이를 저장하는 것이다.
후에 모든 arr값들을 탐색하면서 가장 큰 값을 리턴하는 것이다.

저장방법은 간단하게 생각했다. 이전에 바로 이전에 나온값과 다르다면 arr[x]+=2를 해주는 것이였다.
그렇다면, [5,2,3,3,5,3] 이런경우에서는 올바르게 정답이 리턴 되지만

[1, 1], [1,3,3,2] 라는 반례가 존재했다. 너무 간단하게 생각했던것같다..

두번째로 생각한 방법으로 해결했다!
두번째로 생각한 방법은 map을 사용하는 것이다.
map에 각 숫자들의 index를 저장시킨후에 서로 index간의 차이로 답을 구하는 것이다.
예를 들어서 [5,2,3,3,5,3] 라는 입력이 주어졌다면, 5는 0, 4 라는 인덱스에 위치하고,
2는 1이라는 인덱스에 3은 2,3,5 인덱스에 위치하게된다.
3을 다시 보게되면, 2라는 인덱스는 0, 1 이라는 인덱스에 3이 아닌 다른수가 위치해 있다는 것을 알 수 있기때문에 2 index에 위치한 3 은 왼쪽에서 스타배열을 만들 수 가 있는 것이다!
만약 3이라는 인덱스에있는 원소 3을 본다면 바로 왼쪽 2 인덱스에 위치한 원소 3이 붙어있기때문에 왼쪽으로는 스타배열을 만들지 못하기때문에 오른쪽을 확인해야한다.
오른쪽을 바라보았을때에 5인덱스에 위치한 3까지의 거리는 2 이기때문에 두개의 3 사이에 다른 수가 위치해있다는 것을 알 수 있다.
따라서 3인덱스에 위치한 원소 3은 오른쪽으로 스타배열을 만들 수 가 있는 것이다. 하지만 이때 오른쪽으로 스타배열을 만들어주었기때문에 인덱스 5 에 위치한 원소 3 은 왼쪽방향에서 스타배열을 만들 수가 없는 것이다. 이를 알려주기위해서 left에 1 을 추가해준다!

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

unordered_map<int, vector<int>> um;

int solution(vector<int> a) {
    int answer = -1;
    //map 초기화
    for (int i = 0; i < a.size(); i++) {
        um[a[i]].push_back(i);
    }
    for (auto x : um) {
        int left = 0;
        int right = 0;
        int sum = 0;
        for (int i = 0; i < x.second.size(); i++) {
            //left, right 설정
            if (i == 0) {
                left = -1;
            }
            if (i == x.second.size() - 1) {
                right = a.size();
            }
            else {
                right = x.second[i + 1];
            }
            //스타 배열이 될 수 있는지 판단
            if (x.second[i] - left >= 2) {    //왼쪽에서 만드는 경우
                sum += 2;
                left = x.second[i];
            }
            else if (right - x.second[i] >= 2) { //오른쪽에서 만드는 경우
                sum += 2;
                left = x.second[i] + 1;
            }
            else {  //만들지 못하는 경우
                left = x.second[i] + 1;
            }
        }
        answer = max(answer, sum);
    }

    return answer;
}