한지 - 한조각 쓸모있는 지식 레터

피보나치 수 문제를 풀어보았다

팩토리얼과 마찬가지로

기본적인 재귀함수 구현에 대한 문제였다.

피보나치 수는

F0 = 0;

F1 = 1;

Fn = F(n-1) + F(n-2) 라는 공식이 있다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split(" ");
const value = parseInt(input[0]);

function fibonacci(m, n, arr) {
  const a = arr[0];
  const b = arr[1];

  if (m > n) {
    console.log(b);
  } else {
    const newArr = [b, a + b];
    const _m = m + 1;
    fibonacci(_m, n, newArr);
  }
}

if (value === 0) {
  console.log(0);
} else if (value === 1) {
  console.log(1);
} else {
  fibonacci(2, value, [0, 1]);
}

완전탐색에 해당하는 문제이다.

function solution(answers) {
    var answer = [];
    const score = [
        { name: 1, count : 0 },
        { name: 2, count : 0 },
        { name: 3, count : 0 },
    ];
    const user1 = [1, 2, 3, 4, 5];
    const user2 = [2, 1, 2, 3, 2, 4, 2, 5];
    const user3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
    
    answers.forEach((answer, index) => {
        const value = index + 1;
        if (value < 5) {
            if (answer === user1[index]) score[0].count += 1;
        } else {
            if (answer === user1[index % 5]) score[0].count += 1;
        }
        
        if (value < 8) {
            if (answer === user2[index]) score[1].count += 1;
        } else {
            if (answer === user2[index % 8]) score[1].count += 1;
        }
        
        if (value < 10) {
            if (answer === user3[index]) score[2].count += 1;
        } else {
            if (answer === user3[index % 10]) score[2].count += 1;
        }
    });
    
    score.sort((a,b) => a.count > b.count ? -1 : 1)
    answer = score.filter((val) => val.count === score[0].count).map((val) => val.name);
    
    return answer;
}

위와 같이 문제를 해결해보았다.

1. score를 쉽게 정렬하기위해 배열을 이용했다.

2. 수포자들이 찍기 방식이 일정한 패턴을 가지고 있음을 활용한다. (사실, 랜덤이라면 답을 구하는것 자체가 불가능하지않을까?)

3. 각자의 패턴의 길이만큼은 단순비교를

4. 패턴의 길이 이상에서는 나머지 값을 이용해서 답안과 비교한다.

5. forEach를 이용해 답안의 수 만큼 반복한다.

6. 마지막으로 배열을 정렬하고, 가장 큰 수와 같은 수만큼 답안을 획득한 수포자들만 필터한다.

7. map으로 수포자들의 이름(1,2,3)만 뽑아낸다.

간단하지만,

패턴을 이용한다. 나머지를 이용한다. 와 같은 발상을 못한다면

맞출수없는 문제같다.

마지막으로, 완전탐색의 개념을 살짝 짚어본다.

완전 탐색이란? 가능한 모든 경우의 수를 탐색하고, 확인하는 방법입니다.

function solution(genres, plays) {
    var answer = [];
    let genreArr = [];
    
    genres.forEach((gen, idx) => {
        const currentCnt = plays[idx];
        const hasIdx = genreArr.findIndex(g => g.name === gen);
        if (hasIdx >= 0) {
            genreArr[hasIdx].total += currentCnt;
            genreArr[hasIdx].cntList.push({ order: idx, cnt: currentCnt });
        } else {
            genreArr.push({
                name: gen,
                total: currentCnt,
                cntList: [{ order: idx, cnt: currentCnt }]
            });  
        };
    });
        
    genreArr.sort((a,b) => a.total > b.total ? -1 : 1);
    genreArr.forEach((gen) => {
        gen.cntList.sort((a,b) => a.cnt > b.cnt ? -1 : a.cnt === b.cnt ? 1 : a.cnt < b.cnt ? 1 : -1);
        gen.cntList.slice(0, 2).forEach(({ order }) => answer.push(order));
    });
    
    return answer;
}

1. 장르를  순회하며 새 배열에 필요한 객체 형태로 push해준다.

2. 우리가 알아야 할 값은, 장르별 총합과 index별 플레이 횟수이다.

3. 따라서, name, total, list<{order, cnt}> 구조로 객체를 정의해주었다.

4. 장르 total에 따라서 정렬

5. 장르 내 재생횟수 높은순 -> 고유번호 낮은순으로 정렬

6. 장르별로 두개씩 모아서 앨범을 출시한다고 했으므로, slice(0, 2)하여 출력

* 떠올려본 방법

1. completion을 포문으로 돌린다 + participant에서 해당 index를 찾아 + splice(index, 1) [시간초과]

2. 2중포문으로 비교해나간다. [시간초과]

3. sort를 이용해 각 배열을 정렬 + 순서대로 비교해가며 다를때 리턴 [성공]

function solution(participant, completion) {
  participant.sort();
  completion.sort();
    
  for (let i=0; i<participant.length; i++) {
    if (participant[i] !== completion[i]) {
      return participant[i];
    }
  }
}