🔎 스타수열

❓ 문제링크

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

📄 제출 코드

function solution(a) {
  var answer = -1;
  // 1. 가장 많이 사용된 원소 찾기, [원소, 사용횟수]
  const star = makeStar(a);
  console.log(star);
  
  for (let i = 0; i < star.length; i++) {
    if (answer >= star[i][1]) continue;
    let count = 0;
    for (let j = 0; j < a.length; j++) {
      if (a[j + 1] == undefined) continue;
      if (a[j] == a[j + 1]) continue;
      if (a[j] != star[i][0] && a[j + 1] != star[i][0]) continue;
      count++;
      j++;
    }
    answer = Math.max(answer, count);
    console.log(`answer : ${answer}`)
  }

  return answer*2;
}
function makeStar(a) {
  const arr = a.reduce((acc, cur) => {
    // console.log(acc);
    // console.log(cur);
    acc[cur] ? acc[cur][1]++ : acc[cur] = [cur, 1];
    return acc;
  }, []).filter(el => el).sort((a, b) => b[1] - a[1]);
  return arr;
}

이번 문제는 문제 이해를 못해서 다른사람의 풀이를 보고 이해해 나갔다.

스타수열

• 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} 이고, 각 집합 내의 숫자들이 서로 다르기 때문입니다.

이 문제에서 우리가 구할 것은 스타수열의 최대값이다.
최대값을 구하려면 가장 많이 사용된 원소를 최소한의 교집합 원소로 구성해주어야 한다.
가장 많이 사용된 원소가 부분집합의 한자리를 차지하고, 이 값과 일치하지 않는 어떤 수라도 넣을수 있다면 스타 수열의 조건을 만족할 때 최대길이가 된다.

먼저 가장 많이 사용한 원소순서로 배열을 정렬 해줄 것이다.
배열은 [원소, 횟수]로 구성 된다.

function makeStar(a) {
  const arr = 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]);
  return arr;
}

filter를 안해주면, <empty items>가 생겨서 filter로 값이 있는 친구들만 걸러준다.
정렬을 통해서 가장 많이 사용된 원소부터 먼저 검사를 해주고, 앞에서부터 스타수열이 성립한다면 나머지 반복은 피해줄 수 있다.

이제 스타수열을 찾아보자.
일단 우리가 찾을 건 스타수열의 최대값이기 때문에 이전 값이 현재값보다 작거나 같으면 검사할 필요없다.

if (answer >= star[i][1]) continue;

스타수열의 모든 부분집합은 단 2개로만 구성되어 있기 때문에 현재 위치가 j라면 j+1과 스타수열을 충족하기 위한 조건을 비교해야 한다.
조건은 다음과 같다.

1. a[j+1]이 undefined면 continue
2. a[j]와 a[j+1]이 같으면 continue
3. 현재원소 star[j][0]과 a[j],a[j+1]이 모두 다르면 continue
4. 위 3가지를 통과했다면 현재 스타수열갯수 +1, j와 j+1을 검사했으므로 다다음j로 이동.
5. a배열을 다돌고나면 answer와 count를 비교해 최대값으로 갱신

(처음에 조건이 왜 위와 같은지 이해가 안되서 블로그글을 5번넘게 정독한거같다.)
아까 위에서 가장 많이 사용된 원소가 부분집합의 한자리를 차지하고, 이 값과 일치하지 않는 어떤 수라도 넣을수 있다면 스타 수열의 조건을 만족할 때 최대길이가 된다고 하였다.
그렇다. 위 조건은 아까 설명했던 일치하지 않는 수를 찾는 조건이다.

for (let i = 0; i < star.length; i++) {
    if (answer >= star[i][1]) continue;
    let count = 0;
    for (let j = 0; j < a.length; j++) {
      if (a[j + 1] == undefined) continue;
      if (a[j] == a[j + 1]) continue;
      if (a[j] != star[i][0] && a[j + 1] != star[i][0]) continue;
      count++;
      j++;
    }
    answer = Math.max(answer, count);
    console.log(`answer : ${answer}`)
  }

이제 마지막이다.
우리가 구한건 스타수열의 길이가 아니라 스타수열의 개수다.
모든 스타수열은 2개의 원소로 구성되있으므로 마지막에 *2를 해주어야한다.
(넘무어렵당,,)

📘 참고

https://velog.io/@longroadhome/프로그래머스-LV.3-스타-수열-JS