[CodeKata] 프로그래머스: 1.15(토), 스타 수열

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

이후 나올 모범답안에 비해 민망할 정도로 긴 풀이라, 간단하게 설명하겠다...!!

문제전개에 충실하게, checkStarArr(스타수열 판정), combination(부분수열의 조합) 함수들을 만들고 이에 맞는 부분수열을 찾는 방법이다.

const checkStarArr = (a) => {
  let common = [a[0], a[1]];
  
  for (let i = 0 ; i < a.length ; i+=2) {
    if (a[i] === a[i+1]) return false;
    common = common.filter(e => e === a[i] || e === a[i+1]);
    if (!common.length) return false;
  }
  
  return true;
}


function combination(arr, num){
  const res = [];
  if(num === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const rest = arr.slice(idx+1);
    const combinations = combination(rest, num-1);
    const attach = combinations.map((combination) => [v, ...combination]);
    res.push(...attach);
  })
  return res;
}

function solution(a) {
  const len = a.length;  
  if (len % 2 === 0 && checkStarArr(a)) return len;
  if (len < 2) return 0;
  
  let count = len % 2 === 0 ? len-2 : len-1;
  
  while (count > 2) {
    for (let partArr of combination(a,count)) {
      if (checkStarArr(partArr)) {
        console.log(partArr)
        return count
      }
    }
    count -= 2;
  }
  
  return 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://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EC%8A%A4%ED%83%80-%EC%88%98%EC%97%B4-JS

• answer는 정답을 누적할 변수이다. 여기에는 스타수열을 이루는 쌍의 갯수가 누적되므로, 마지막에 *2(총 갯수) 처리를 해야한다.
• counts는 a배열에서 [요소, 사용횟수] 를 가장 많이 사용한 순으로 저장한 배열이다. reduce()를 통해 계산하며, acc의 (요소)번째 인덱스에 정보를 저장하기 때문에, 이후 filter()로 사이사이 undefined를 정리해주는 것이다.
• counts를 순회하며 answer에 정답을 누적한다. 우선, 사용횟수가 answer보다 작다면 정답이 되지 않으므로 continue로 넘어간다.
• 다음으로, 현재조건([요소, 사용횟수]) 와 a배열을 비교한다. count는 스타수열 쌍의 갯수이며, a배열을 순회하며 아래 연산을 한다.
• 1) 다음요소가 없거나, 2) 요소쌍이 서로 같거나, 3) 요소쌍 모두 현재조건 요소와 다른 경우 부적절하므로 continue로 넘어간다. 
• 이를 만족한다면, [a[j], a[j+1]]은 스타수열이 되므로 count에 1을 더한다. 그리고, 다다음 요소를 보기위해 인덱스(j)에 1을 더 더해준다.
• 위 계산을 완료한 뒤, count와 answer 중 최대값으로 최신화를 한다. 이는 스타수열 쌍의 갯수이므로, 정답을 반환할 땐 2를 곱한다.

 

문제의 흐름에 너무 충실한 로직을 짜면 그만큼 효율성이 떨어진다는 것을 다시금 느꼈다.

그대로 구현하는 알고리즘을 짜기보다는, 정답을 위한 조건들을 고려해서 이를 찾을 수 있는 최적의 방법을 고민해버릇 해야겠다!