[프로그래머스] LV.3 스타 수열 (JS)

문제

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

• 어떤 수열 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의 길이) 미만입니다.

입출력 예시

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

풀이

뭔가 굉장히 복잡해 보이는 수열이지만 찬찬히 들여다보면 그렇게까지 복잡하진 않다. (뭐 복잡한건 사실이다 ㅋㅋ)

스타수열을 만들기 위해서는 단순하게 다음을 생각해볼 수 있다.

1. 가장 많이 사용된 원소를 찾는다.
2. 가장 많이 사용된 원소를 스타수열 부분집합에 1개씩 나눠 구성한다 (교집합이 최소 1개 이상이여야 하므로)
3. 구성된 부분집합에 가장 많이 사용된 원소와 서로 다른 수를 최대한 집어 넣는다.
4. 구성이 완료된 부분집합의 개수를 구한다.

우리는 스타수열의 최대 길이를 구하는 것이기 때문에, 이를 위한 가장 기본적인 전제 조건은 원본 배열에서 가장 많이 사용된 원소를 최소한의 교집합 원소로 구성해주는 것이다. 즉 해당 값들이 스타수열 부분집합에서 하나의 자리를 차지하도록 하고, 나머지 값은 이 값과 일치하지 않는 어떠한 수를 넣을 수만 있다면 스타수열의 조건을 충족하면가 가장 최대 길이가 될 것이다.

그러나 위에서 3번 조건에서 최대 원소 값과 다른 수의 개수가 부족할 수 있다. 예를 들어 0이라는 숫자가 원본 배열에서 100번이 사용되었다고 가정하자. 그리고 1, 2, 3 이라는 각각의 숫자가 각자 10번씩 사용되었다고 가정하자.

그렇다면 스타수열을 만들기위해 100개의 0이 들어간 부분집합이 만들어질 것이다. 그리고 나머지 한 칸을 채우기 위해서 0과 다른 숫자들을 하나씩 넣어줄텐데 우리가 가진 0과 다른 숫자는 총 30개뿐이다. 따라서 100개의 스타수열을 만들 수가 없다. 이러한 경우까지 모두 포함하여 계산을 해주어야 하기 때문에 사용된 모든 원소에 대해 검사를 실시하되 적절한 가지치기를 통해 효율성을 극복하도록 해보자.

먼저 앞에서 언급했듯이 가장 많이 사용된 원소를 찾아줄 것이다. 뿐만아니라 가장 많이 사용된 원소를 모두 커버하지 못할 경우를 대비해 [ 원소, 사용횟수 ] 의 형태로 배열을 만들어 사용횟수 기준으로 내림차순 정렬을 해주자. 그러면 우리는 반복문에서 가장 많이 사용된 원소부터 먼저 검사를 해주고 앞에서부터 스타수열이 성립한다면 나머지 반복은 피해줄 수 있을 것이다. 여기서는 배열의 형태로 원소값과 사용횟수를 저장하지만 Object의 형태로 { "원소값" : "사용횟수" }의 형태로 저장해도 상관없다.

const counts = a.reduce((acc, cur) => {
  // 현재 원소 cur이 이전에 사용된 적 있다면
  // 사용횟수를 1씩 증가시키고
  // 사용된 적이 없다면 초기값으로 세팅
  acc[cur] ? acc[cur][1]++ : acc[cur] = [cur, 1];
  return acc;
}, []).filter(el => el).sort((a, b) => b[1] - a[1]);
// 배열 index로 (acc[cur]) 만들어주므로 중간중간 undefined 값이 발생
// 이러한 무효값을 한번 걸러주고 (filter)
// 사용횟수 기준으로 내림차순 정렬 실시

위의 과정을 마치면 변수 counts에는 각 원소값과 그 원소의 사용횟수가 내림차순으로 모두 저장되어 있을 것이다. 그렇다면 이 값을 가지고 우리는 처음에 언급한 조건대로 스타수열을 찾아줄 수 있다. 위에서 말한 조건을 조금 더 세분화해보자.

1. 현재 counts[i][1], 즉 현재 사용횟수보다 이전에 만든 스타수열의 개수(= answer)가 크거나 같은 경우 검사할 필요가 없다. 우리가 필요한 건 최댓값이기 때문!

2. 주어진 배열 a의 길이만큼 내부에서 반복문을 돌면서 다음을 체크한다.

   2-1. a[j]+1이 undefined 라면 continue

   2-2. a[j] 와 a[j+1]이 같으면 continue

   2-3. a[j]와 a[j+1] 모두 현재 원소(counts[i][0])과 다르면 continue

3. 위 조건을 모두 통과했다면 스타수열 값 +1(= count++) 하고 다다음 j로 넘어가 탐색

4. 내부 반복문이 끝나면 현재 스타수열의 개수(= count)와 기존 스타수열 최댓값(= answer)을 비교하여 최댓값 갱신

위 과정을 그대로 코딩하면 되겠다. 이때 a[j+1]과 비교하는 이유는 스타수열의 조건때문이다. 스타수열의 모든 부분집합은 단 2개로만 구성되어 있기 때문에 현재 위치가 j라면 j+1과 스타수열을 충족하기 위한 조건을 비교해야 한다.

for(let i = 0; i < counts.length; i++) {
  // 이미 스타수열의 값이 현재 원소의 사용횟수와
  // 크거나 같다면 검사할 필요가 없다.
  if(answer >= counts[i][1]) continue;
  
  // 현재 원소값을 기준으로 만들어지는 스타수열 개수
  let count = 0;
  
  for(let j = 0; j < a.length; j++) {
    if(a[j+1] === undefiend) continue;
    if(a[j] === a[j+1]) continue;
    if(a[j] !== counts[i][0] && a[j+1] !== counts[i][0]) continue;
    
    // 위 조건을 모두 통과하면 스타수열 조건 충족
    // 따라서 개수를 하나 늘리고
    // j+1 범위까지 계산했으므로 다다음 j 위치로 이동
    count++;
    j++;
  }
  
  // 기존의 스타수열 개수와 새롭게 계산한 개수 중에
  // 더 큰 값으로 갱신
  answer = Math.max(answer, count);
}

이때 정답을 리턴함에 있어 주의해야 할 것이 있다. 위에서 우리가 구해준 것은 스타수열의 길이가 아닌 스타수열의 개수이다. 모든 스타수열은 원소가 2개이기 때문에 최종적으로 스타수열의 길이는 우리가 구해준 스타수열 개수에 2를 곱해준 값이 된다. 주석을 제외한 전체 코드는 다음과 같다.

function 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]) 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] !== counts[i][0] && a[j+1] !== counts[i][0]) continue;
      
      count++;
      j++;
    }
    
    answer = Math.max(answer, count);
  }
  
  return answer * 2;
}

출처

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