스타 수열 (Javascript)

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

프로그래머스

문제의 조건과 예시는 아래와 같다.

1. x의 길이를 2n이라 할 때, 다음과 같은 n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다.
2. x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1] 입니다.
3. x의 길이가 2 이상의 짝수입니다. (빈 수열은 허용되지 않습니다.)
예를 들어, [1,2,1,3,4,1,1,3]은 스타 수열입니다. {1,2}, {1,3}, {4,1}, {1,3} 의 교집합은 {1} 이고, 각 집합 내의 숫자들이 서로 다르기 때문입니다.

풀이

1. 만약 전체 탐색을 한다면 만들 수 있는 길이가 2인 수열 집합들을 모두 찾은 후 탐색 알고리즘을 통해 최대 길이를 찾을 수 있을 것이다.
2. 하지만 a의 길이가 50만으로 길기 때문에 전체 탐색을 시도한다면 시간 초과가 발생 할 수 있다.
3. 때문에 각각의 원소들의 등장한 횟수를 기준으로 정렬을 시도한다.
4. 이후 가장 많이 등장 한 원소부터 해당 값을 교집합으로 삼는다는 생각으로 만들 수 있는 스타 수열을 찾아본다. 
5. 이 때 만들 수 있는 스타 수열의 길이의 최댓값을 저장한다.
6. 만약. 5번에서 구했던 최댓값이 4번에서 말했던 교집합으로 삼을려던 길이보다 크다면 이후 어떠한 수를 교집합으로 삼더라도 등장할 수 있는 길이보다 짧다는 것이므로 반복문을 멈춰준다.

// 1. x의 길이를 2n이라 할 때, 다음과 같은 n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다.
// 2. x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1] 입니다.
// 3. x의 길이가 2 이상의 짝수입니다. (빈 수열은 허용되지 않습니다.)
// 예를 들어, [1,2,1,3,4,1,1,3]은 스타 수열입니다. {1,2}, {1,3}, {4,1}, {1,3} 의 교집합은 {1} 이고, 각 집합 내의 숫자들이 서로 다르기 때문입니다.

const solution = (a) => {
    let answer = 0;
    const counts = a
        .reduce((acc, cur) => {
            acc[cur] ? acc[cur][1]++ : (acc[cur] = [cur, 1]);
            return acc;
        }, [])
        .filter((el) => el)
        .sort((a, b) => b[1] - a[1]);

    for (let i = 0; i < counts.length; i++) {
        if (answer >= counts[i][1]) break;

        let count = 0;

        for (let j = 0; j < a.length - 1; j++) {
            if (a[j] === a[j + 1]) continue; // 앞뒤가 같으면 조건 2에 부합하지 않음
            if (a[j] !== counts[i][0] && a[j + 1] !== counts[i][0]) continue; //교집합의 원소의 개수가 없으면 조건 1 안맞음

            count++;
            j++;
        }

        answer = Math.max(answer, count);
    }

    return answer * 2;
};

console.log(solution([0, 3, 3, 0, 7, 2, 0, 2, 2, 0]));