[Algorithm] 스타 수열

📋 문제

다음과 같은 것들을 정의합니다.

• 어떤 수열 x의 부분 수열(Subsequence)이란, x의 몇몇 원소들을 제거하거나 그러지 않고 남은 원소들이 원래 순서를 유지하여 얻을 수 있는 새로운 수열을 말합니다.
  
  • 예를 들어, [1,3]은 [1,2,3,4,5]의 부분수열입니다. 원래 수열에서 2, 4, 5를 제거해서 얻을 수 있기 때문입니다.
• 다음과 같은 조건을 모두 만족하는 수열 x를 스타 수열이라고 정의합니다.
  
  • 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} 이고, 각 집합 내의 숫자들이 서로 다르기 때문입니다.

 

1차원 정수 배열 a가 매개변수로 주어집니다. a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 길이를 return 하도록 solution 함수를 완성해주세요. 이때, a의 모든 부분 수열 중에서 스타 수열이 없다면, 0을 return 해주세요.

제한사항

• a의 길이는 1 이상 500,000 이하입니다.
  
  • a의 모든 수는 0 이상 (a의 길이) 미만입니다.

입출력 예

[0]	0
[5,2,3,3,5,3]	4
[0,3,3,0,7,2,0,2,2,0]	8

 

✏️ 풀이

다른 사람들의 풀이를 참고했다. 보면서 깨달은 사실인데 내가 문제를 잘못 이해했음을 알게 되었다. 문제의 지문 중에 각 집합 내의 숫자들이 서로 달라야 한다는 것을 만약 {1, 2}, {1, 2}로 각 집합의 다른 숫자들이 같으면 안된다고 이해했었다...

 

a의 길이가 500,000이기 때문에 모든 경우를 탐색하는 것은 당연히 안될 것이라고 생각었했다. 풀이를 보고서 깨달은 점이 가장 가능성이 큰 숫자부터 탐색하면 효과적으로 경우의 수를 줄일 수 있다는 점이었다. 따라서 a 수열에서 가장 많이 나온 숫자부터 탐색한다. 만약 (1, 3, 3, 2, 3, 2, 2, 2, 2, 2, 2, 2) 이런 경우 2가 제일 많이 등장하지만 답은  {1, 3}, {3, 2}, {3, 2}으로 6이 된다. 하지만 2를 한번 탐색하고 다음으로 많이 등장하는 3을 기준으로 탐색하기 때문에 경우의 수가 줄어든다. 이는 수열의 길이가 길수록 효과적일 것이라고 생각한다. 따라서 배열을 돌며 Map에 저장했다. (Map을 사용한 이유는 최근 문제를 풀면서 삽입, 삭제가 많이 등장할수록 객체({})보다는 Map이 더 큰 효율성을 보임을 알게 되었기 때문!) 그리고 배열로 변환 후에 등장한 횟수를 기준으로 내림차순으로 정렬했다.

 

이제 이 정렬된 배열을 반복문으로 돌며 수타수열의 기준이 되는 수를 바꿔주며 탐색한다. a 배열을 처음부터 끝까지 돌면서 두 개의 요소를 비교하며 기준에 부합할때 수열의 길이에 2를 더해준다.

 

• 하나의 수는 스타수열의 기준이 되는 수이여야 한다.
• 인접한 두 수가 동일하면 안된다.

이에 부합하면 스타수열의 길이를 의미하는 starCnt를 2 증가시켜줬다. 그리고 해당 인덱스까지 스타수열의 요소로 빠지므로 추가적으로 1의 인덱스를 증가시켜줬다.

 

 만약 현재의 answer보다 현재 스타수열의 기준이 되는 수의 등장 회수 * 2가 적다면 절대 최대값 갱신을 할 수 없으므로 반복문을 종료한다.

 

몇가지 경우의 예시를 들어 설명하면 다음과 같다.

1. (1, 2, 2, 2, 4, 4)의 경우 (맨 처음 2를 기준)
   • 맨 처음에 1, 2를 비교 -> 스타수열이 될 수 있음(2까지는 비교할 수 없으므로 인덱스를 추가적으로 1증가)
   • 2, 2 비교 -> 스타수열이 될 수 없음 패스
   • 2, 4 비교 -> 스타수열이 될 수 있음
   • {1, 2}, {2, 4}로 답은 4
2. (1, 2, 1, 3, 4, 4, 4, 4, 4)의 경우 (맨 처음 4를 기준)
   • 1, 2 비교 -> 스타수열이 되는 기준 수(4)가 없으므로 패스(이후로도 쭉 패스)
   • 3, 4 비교 -> 스타수열이 될 수 있음
   • 4, 4 비교 -> 값이 같으므로 스타수열이 될수 없음(이후로도 마찬가지)
   • {3, 4}로 스타수열 구성
   • 다음으로 많은 수 1을 기준으로 다시 반복(현재 answer = 2, 1의 개수 2)
   • 1, 2비교 -> 스타수열이 될 수 있음
   • 1, 3 비교 -> 스타수열이 될 수 있음
   • 4, 4 비교 -> 스타수열이 될 수 없음 패스(이후 마찬가지)
   • {1, 2}, {1, 3}으로 답은 4

 

⌨️ 코드

function solution(a) {
  var answer = -1;

  const hash = new Map();
  for (const num of a) {
    hash.set(num, (hash.get(num) || 0) + 1);
  }

  const hashArr = [...hash.entries()].sort((a, b) => b[1] - a[1]);

  for (const [num, cnt] of hashArr) {
    if (answer > cnt * 2) break;

    let starCnt = 0;
    for (let i = 1; i < a.length; i++) {
      if (a[i - 1] === a[i]) continue;
      if (a[i - 1] !== num && a[i] !== num) continue;

      starCnt += 2;
      i += 1;
    }
    answer = Math.max(answer, starCnt);
  }

  return answer;
}