코플릿 - 알고리즘 문제

01_[Greedy] 짐 나르기

//<레퍼런스>
function movingStuff(stuff, limit) {
  let twoStuff = 0;
  let sortedStuff = stuff.sort((a, b) => a - b);

  let leftIdx = 0;
  let rightIdx = sortedStuff.length - 1;

  while(leftIdx < rightIdx) {
      if(sortedStuff[leftIdx] + sortedStuff[rightIdx] <= limit) {
          leftIdx++;
          rightIdx--;
          twoStuff++;
      } else {
          rightIdx--;
      }
  }
  return stuff.length - twoStuff;
}

02_[Greedy] 편의점 알바

// <레퍼런스>
function partTimeJob(k) {
  let result = 0;
  const wallet = [500, 100, 50, 10, 5, 1];
  for(let i = 0; i < wallet.length; i++) {
    if(k > 0) {
      const sum = Math.floor(k / wallet[i]);
      result += sum;
      k = k - (wallet[i] * sum);
    }
  }
  return result;
}

// <내 풀이>
function partTimeJob(k) {
  // TODO: 여기에 코드를 작성하세요.
  let arr = [500, 100, 50, 10, 5, 1];
  let count = 0;
  let result = k;
  for(let i = 0; i < arr.length; i++){
    if( result >= arr[i]){
      count = count + (Math.floor(result / arr[i])); 
      result = k % arr[i];
    }
  }
  return count;
}

03_[구현] 보드 게임

// <내 풀이>
function boardGame(board, operation) {
  // TODO: 여기에 코드를 작성하세요.
  const M = board.length, N = board[0].length;
  // const isValid = (row, col) => row < M && row >= 0 && col < N && col >= 0
  let row = 0, col = 0;
  let result = 0;
  
  for(let i = 0; i < operation.length; i++){
    if(operation[i] === 'R' && col+1 < M){
      col = col + 1;
      result = result + board[row][col]
    } else if(operation[i] === 'L' && col-1 >= 0){
      col = col - 1;
      result = result + board[row][col]
    } else if(operation[i] === 'D' && row+1 < N){
      row = row + 1;
      result = result + board[row][col]
    } else if(operation[i] === 'U' && row-1 >= 0){
      row = row - 1;
      result = result + board[row][col]
    } else return 'OUT'
  }

  return result;
};

// <레퍼런스>
// LOOK UP TABLE을 사용한다면 조건문을 추상화시킬 수 있습니다.
function boardGame(board, operation) {
  // TODO: 여기에 코드를 작성하세요.
  const DIR = {
    'U': [-1, 0],
    'D': [1, 0],
    'L': [0, -1],
    'R': [0, 1]
  }
  const LEN = board.length;
  const isValid = (y, x) => 0 <= y && y < LEN && 0 <= x && x < LEN;

  let Y = 0;
  let X = 0;
  let score = 0;
  for (let i = 0; i < operation.length; i++) {
    const [dY, dX] = DIR[operation[i]];
    Y += dY;
    X += dX;
    if (isValid(Y, X) === false) return 'OUT';
    score += board[Y][X];
  }
  return score;
};

04_(Advanced) [DP] 금고를 털어라

• 해설

function ocean(target, type) {
  let bag = [1]; 
  for(let i = 0; i <= target; i++) bag.push(0)
  for(let i = 0; i < type.length; i++){
    for(let j = 1; j <= target; j++){
      if( type[i] <= j){
        bag[j] = bag[j] + bag[j - type[i]]
      }
    }
  }
  return bag[target];
}

// <주석있는 레퍼런스>
function ocean(target, type) {
  // bag 이라는 배열에 금액을 만들 수 있는 경우의 수를 기록
  // 각 인덱스 no# = 만드려는 금액 을 의미
  // ex) target = 5, type = [1, 2, 5] 면
  // bag[3] = 2  => 3을 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용
  // bag[4] = 2  => 4를 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용
  // bag[5] = 4  => 5를 만드는 경우의 수 = 1*5 , 1*3 + 2, 1 + 2*2, 5*1
  // 0 을 만들 수 있는 경우는 아무것도 선택하지 않으면 되기 때문에 bag[0] = 1 로 초기값 설정
  let bag = [1];

  // 인덱스 no# = 만드려는 금액 이기 때문에
  // bag 을 target 금액만큼의 길이를 가진 배열을 만들어 주고,
  // 경우의 수를 저장하기 위해 초기값은 모두 0으로 만들어 준다
  for(let i = 1; i <= target; i++)
    bag[i] = 0;
  // 돈의 종류가 담겨있는 배열을 순차적으로 탐색   
  for(let i = 0; i < type.length; i++) {
  // target 금액까지 순차적으로 1씩 증가하면서    
    for(let j = 1; j <= target; j++)
  // bag의 인덱스가 type[i] 보다 큰 구간만
  // (작은 구간은 type[i]로 만들 수 없는 금액이기 때문에 탐색할 필요가 없다)    
      if(type[i] <= j)
  // 기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해준다       
        bag[j] += bag[j-type[i]];
  }
  // bag 의 target 인덱스에 target 금액을 훔칠 수 있는 경우의 수가 쌓이므로
  // 해당 값을 리턴해 준다
  return bag[target];
}

05_[중복순열] 가위바위보

function  rockPaperScissors(selectNumber) {

  if(selectNumber === undefined) selectNumber = 3;

  const result = [];
  let lookup = ['rock', 'paper', 'scissors'];

  function recursion(count, bucket){
    if(count === 0){
      result.push(bucket);
      return;
    }
    for(let i = 0; i < 3; i++){
      const pick = lookup[i];
      recursion(count-1, bucket.concat(pick));
    }
  }
  recursion(selectNumber, []);

  return result; 
}
  // if (selectNumber === 1) return arr.map((el) => [el]); 
  // arr.forEach((fixed, index, origin) => {
  //   // const rest = origin
  //   // 일반 순열알고리즘에서 위의 rest 만 origin로 바뀐다
  //   const permutations = rockPaperScissors(selectNumber - 1); 
  //   const attached = permutations.map((el) => [fixed, ...el]); 
  //   results.push(...attached); 
  // });

// < 내 풀이>
function rockPaperScissors (rounds) {
  // TODO: 여기에 코드를 작성합니다.
  rounds = rounds || 3;
  let result = [];
  const lookup = ['rock', 'paper', 'scissors'];

  function recursion(count, bucket){
    if(count === 0){
      result.push(bucket);
      return;
    }
    for(let i = 0; i < 3; i++){
      const pick = lookup[i];
      recursion(count-1, bucket.concat(pick));
    }
  }

  recursion(rounds, []);
  return result;
};

// <레퍼런스>
// Advanced가 포함된 레퍼런스 코드입니다.
const rockPaperScissors = function (rounds) {

  // rounds 매개변수를 임의로 넣습니다.
  // rounds 변수가 있을 경우 그대로 사용하고, 없다면 3(기본)을 사용합니다.
  rounds = rounds || 3;
  const rps = ['rock', 'paper', 'scissors'];

  // 결과를 담을 배열 선언
  const outcomes = [];

  // 재귀를 사용할 함수 선언
  // rounds를 넣을 변수 roundsToGo, 일회용 배열인 playedSoFar 변수를 선언합니다.

  // 재귀를 사용하는 이유는, 배열의 모든 요소의 경우의 수를 훑기 위한 적절한 방법이기 때문입니다.
  // 간단히 말하자면, 이 함수는 rounds 숫자를 기준으로, 일회용 배열에 rps 요소를 rounds 숫자만큼 넣게 됩니다.
  // 이 로직을 잘 이해할 수 있을 때까지 하단의 함수 로직을 연구해야 합니다.
  let permutate = function (roundsToGo, playedSoFar) {

    // rounds가 0일 경우 outcones 배열에 삽입하고, 재귀에서 빠져나옵니다.
    if (roundsToGo === 0) {
      outcomes.push(playedSoFar);
      return;
    }

    // rps 배열을 한 번씩 순회합니다.
    for (let i = 0; i < rps.length; i++) {
      // rps의 i번째 요소를 변수에 담아서
      let currentPlay = rps[i];
      // permutate(본인)에 기존 rounds에서 하나 뺀 숫자와, 일회용 배열 playedSoFar에 currentPlay를 삽입하여 재귀를 실행합니다.
      // rounds에서 하나를 빼는 이유는, 일회용 배열의 크기를 rounds만큼 맞춰주기 위함입니다. [rock, rock, rock]

      // Q. playedSoFar.push(currentPlay)로 할 수 있을 텐데, 왜 concat을 사용할까요?
      permutate(roundsToGo - 1, playedSoFar.concat(currentPlay));
      /**
       * 이 재귀의 로직은 이렇습니다. 처음 실행된 반복문은 rps를 전부 순회해야 끝이 납니다.
       * 그러나 한 번 반복할 때마다 permutate 함수가 실행되고, rounds의 숫자는 짧아지며, playedSoFar에 요소가 계속 쌓일 것입니다.
       * 결국, roundsToGo가 0이 될 때까지 이 반복문은 rps[i]가 0일 것이며, playedSoFar에는 [rock, rock, rock]이 되어 outcones에 Push하고, 종료하게 됩니다.
       * return이 되었으니, 한 번의 재귀 호출이 끝났습니다. 마지막 호출 바로 전으로 돌아가,
       * for문은 i = 1을 가리키게 될 것이고, [rock, rock, paper]을 삽입한 뒤 호출을 하게 됩니다.
       * roundsToGo가 0이 되어, 해당 배열은 outcomes 배열에 삽입됩니다.
       * 이런 식으로 모든 호출의 반복문이 끝날 때까지 반복하며 outcomes에 경우의 수 요소들이 담기게 됩니다.
       */
    }
  };

  // 함수를 실행합니다.
  permutate(rounds, []);

  // outcomes를 반환합니다.
  return outcomes;
};

06_[순열] 새로운 치킨 소스 레시피

function newChickenRecipe(stuffArr, choiceNum) {
  // TODO: 여기에 코드를 작성하세요.

  // stuffArr : 0이 3개인 재료는 탈락
  // [1, 10, 11000, 1111]
  stuffArr = stuffArr.filter((el) => {
    let count = 0;
    let strArr = el+''; //[1, 0]
    for(let i = 0; i < strArr.length; i++){
      if(strArr[i] === '0') count++;
    }
    if(count < 3) return el; 
  })
  //
  if(stuffArr.length < choiceNum) return [];
  //
  let result = [];
  function recursion(count, bucket){
    if(count === 0){
      result.push(bucket);
      return;
    }
    for(let i = 0; i < stuffArr.length; i++){
      if(bucket.includes(stuffArr[i])) continue;
      const pick = stuffArr[i];
      recursion(count-1, bucket.concat(pick));
    }
  }
  recursion(choiceNum, []);
  return result;
}

// if (choiceNum === 1) return stuffArr.map((v) => [v]);

//   stuffArr.forEach((v, idx, stuffArr) => {
//     const fixer = v;
//     const restArr = stuffArr.filter((_, index) => index !== idx);
//     const permuationArr = newChickenRecipe(restArr, choiceNum - 1);
//     const combineFixer = permuationArr.map((v) => [fixer, ...v]);
//     result.push(...combineFixer);
//   });
//   return result;

// <레퍼런스>
function newChickenRecipe(stuffArr, choiceNum) {
  // stuffArr에서 0이 3개 이상이라면 전부 필터로 거르기.
  let freshArr = [];

  for (let i = 0; i < stuffArr.length; i++) {
    const element = String(stuffArr[i])
      .split('')
      .filter((e) => e === '0');
    if (element.length <= 2) {
      freshArr.push(stuffArr[i]);
    }
  }

  // 정렬
  freshArr.sort((a, b) => a - b);

  // 엣지 케이스 처리
  if (freshArr.length === 0 || freshArr.length < choiceNum) return [];

  // 레시피 초기화
  let result = [];

  // freshArr를 상대로 순열 구하기
  const permutation = (arr, bucket, n) => {
    if (n === 0) {
      result.push(bucket);
      return;
    }

    for (let i = 0; i < arr.length; i++) {
      // 하나를 초이스함
      const choice = arr[i];
      // 배열을 슬라이스함
      const sliceArr = arr.slice();
      // 초이스만 뺀다
      sliceArr.splice(i, 1);
      // 재귀
      permutation(sliceArr, bucket.concat(choice), n - 1);
    }
  };

  // 실행
  permutation(freshArr, [], choiceNum);
  
  // 순열의 길이 반환
  return result;
}

// <내 풀이>
function newChickenRecipe(stuffArr, choiceNum) {
  // TODO: 여기에 코드를 작성하세요.

  stuffArr = stuffArr.filter(el => {
    let count = 0;
    let str = `${el}`;
    for(let i = 0; i < str.length; i++){
      if(str[i] === '0') count++
      if(count >= 3) break;
    }
    return count < 3
  })
  stuffArr.sort((a, b) => a - b)

  if(stuffArr.length < choiceNum || stuffArr.length === 0) return [];

  let result = [];
  function aux(count, bucket, arr) {
    if(count <= 0){
      result.push(bucket)
      return;
    }
    for(let i = 0; i < arr.length; i++){
      let pickup = arr[i]
      let newBucket = bucket.concat(pickup)
      // bucket = bucket.concat(pickup)하면 오류난다.. 왜 ? 
      const sliceArr = arr.slice();
      sliceArr.splice(i, 1)
      aux(count-1, newBucket, sliceArr);
    }
  }

  aux(choiceNum, [], stuffArr)
  return result;
}

07_[조합] 블랙잭은 지겨워

// <내 풀이>
function boringBlackjack(cards) {
  // TODO: 여기에 코드를 작성합니다.
  
  let count = 0;
  let len = cards.length;
  for(let i = 0; i < len; i++){
    for(let j = i+1; j < len; j++){
      for(let k = j+1; k < len; k++){
        const num = cards[i] + cards[j] + cards[k];
        if(isPrime(num)) count++;
      }
    }
  }


  function isPrime(num) {
    if(num === 2) {
      return true;
    }
    for(let i = 2; i <= Math.floor(Math.sqrt(num)); i++){
      if(num % i === 0){
        return false; 
      }
    }
    return true; 
  }

  return count;
}

// <레퍼런스>
function boringBlackjack(cards) {
  let count = 0;

    // 1. cards 에서 카드 3장 뽑기
    let length = cards.length;
    // 카드 뽑는 방식은 첫 카드를 cards 의 0번 index 부터 고정해 놓고 1씩 뒤로 옮겨간다
    for (let i = 0; i < length; i++) {
    // 두 번째 카드의 인덱스는 첫 카드 + 1에서 시작해야 하고
      for (let j = i + 1; j < length; j++) {
    // 세 번째 카드의 인덱스는 두 번째 카드 + 1에서 시작해야 한다 
        for (let k = j + 1; k < length; k++) {
          const number = cards[i] + cards[j] + cards[k];
          // 세 카드의 합이 소수이면 경우의 수 + 1
          if (isPrime(number)) count++;
        }
      }
    }
  
    //2. 소수 판별
    function isPrime(number) {
    // 2부터 비교하기 시작해서 나누어 떨어지는 수가 있으면 소수가 아니다
    // for 문 조건을 number/2 로 해도 되는 이유는 i > number/2 가 되면 몫이 절대 0이 될수 없기 때문에
    // number/2 까지만 비교해 보아도 소수 판별이 가능하다
      for (let i = 2; i < number/2; i++) {
        if (number % i === 0) return false;
      }
      return true;
    }
  
    return count;
}

function boringBlackjack(cards) {
  let newArr = [];
  
  function recursion(count, bucket, k){
    if(count === 0){
      let sum = bucket.reduce((pre, cur) => pre + cur);
      newArr.push(sum);
      return;
    }
    for(let i = k; i < cards.length; i++){
      const pick = cards[i];
      recursion(count-1, bucket.concat(pick),++k);
    }
  }
  recursion(3, [], 0);
  
  const notprime = newArr.filter(el => {
    for(let i = 2; i < el/2; i++){
      if(el % i === 0 ) return el;
    }
  })
  console.log(newArr.length)
console.log(notprime.length)
  let num = newArr.length - notprime.length;
  return num;

}

  // TODO: 여기에 코드를 작성합니다.
  // 조합
  // 카드 여러장 받아서
  // 3장 뽑아서 더한다
  // 더한값을 배열로 저장

  // 그리고 저장된 배열이 소수인지 확인해서
  // 소수인 값의 개수를 리턴

  // for (let i = 0; i< cards.length; i++){
  //   for (let n = i +1; n < cards.length; n++){
  //     for (let m = n +1; m < cards.length; m++){
  //       const number = cards[i] + cards[n] + cards[m];
  //       newArr.push(number);
  //     }
  //   }
  // }
 

08_[GCD] 빼빼로 데이

// <내풀이>
function divideChocolateStick(M, N) {
  // TODO: 여기에 코드를 작성합니다.
  // 공약수 구하기.
  function GCD(M, N){
    if( M % N === 0 ) return N;
    return GCD( N,  M % N );
  }
  let gcdNum = GCD(M,N)

  let arr = [];
  for(let i = 1; i <= Math.floor(Math.sqrt(gcdNum)); i++){
    if( gcdNum % i === 0 && gcdNum / i !== Math.sqrt(gcdNum)) arr.push(i, gcdNum/i);
    if( gcdNum / i === Math.sqrt(gcdNum)) arr.push(Math.sqrt(gcdNum));
  }
  arr.sort((a, b) => a-b);

  arr = arr.map(el => {
    return [el, M / el, N / el]
  })

  return arr;
}

// <레퍼런스>
// 최대 공약수(유클리드 호제법: Euclidean algorithm)
function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}

function divideChocolateStick(M, N) {
  const result = [];
  // 최대공약수를 구한다.
  // M, N의 순서는 상관없다.
  const GCD = gcd(M, N);
  let temp = 0; //

  // 약수는 대칭적이므로 제곱근까지만 반복해도 된다.
  // 예) 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이다.
  // 제곱근을 기준으로 양쪽의 값 하나씩 곱했을 때 36이 되기 때문에
  // 제곱근 보다 큰 약수는 제곱근보다 작은 약수에서 구할 수 있다.
  const sqrt = Math.floor(Math.sqrt(GCD));
  for (let left = 1; left <= sqrt; left++) {
    if (GCD % left === 0) {
      // 최대공약수의 약수인 경우 중 제곱근 보다 작은 약수의 경우
      result.push([left, M / left, N / left]);
      if (left * left < GCD) {
        // 제곱근이 아닌 경우(제곱근 보다 작은)
        right = GCD / left; // 최대 공약수를 제곱근이 아닌 수로 나누면 제곱근 보다 큰 약수를 구할 수 있다.
        result.push([right, M / right, N / right]);
      }
    }
  }

  // '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬
  result.sort((op1, op2) => op1[0] - op2[0]);

  return result;
}

09_(Advanced) [멱집합] 집밥이 그리워

// <내풀이>
function missHouseMeal(sideDishes) {
  // TODO: 여기에 코드를 작성합니다.
  // []에 sideDishes[0] 추가 
  // result = [[], [sideDishes[0]]]
  // result = result + (result에 sideDishes[1] 추가). 
  // ... sideDishes.length-1 까지 반복
  sideDishes.sort()
  let result = [[]];
  let addResult = [];
  for(let i = 0; i < sideDishes.length; i++){
    for(let j = 0; j < result.length; j++){
      addResult.push(result[j].concat(sideDishes[i]))
    }
    result.push(...addResult)
    addResult = []
  }
  return result.sort();
}

// <레퍼런스>
function missHouseMeal(sideDishes) {

  // 결과를 담을 배열을 선언합니다.
  let result = [];
  // sideDishes를 사전식 순서로 정렬합니다.
  sideDishes.sort();

  // 모든 조합을 검사하는 재귀 함수를 작성합니다.
  const sidePowerSet = (idx, sideDish) => {

    // 재귀 함수이기 때문에 탈출 조건을 만듭니다.
    if (idx === sideDishes.length) {
      // 만약, idx와 sideDishes의 길이가 같다면(마지막까지 검토한 경우) result에 sideDish를 삽입하고 push합니다.
      result.push(sideDish);
      return;
    }

    // idx번째 요소가 포함되지 않는 경우
    sidePowerSet(idx + 1, sideDish);

    // idx번째 요소가 포함되는 경우
    sidePowerSet(idx + 1, [...sideDish, sideDishes[idx]]);
  };

  // 0 번째 인덱스와 빈 배열을 인자로 받는 재귀 함수를 실행합니다.
  sidePowerSet(0, []);
 // sidePowerSet(1, []);
// sidePowerSet(1, [sideDishes[0]])

//->sidePowerSet(2, []);
//->sidePowerSet(2, [sideDishes[1]])
//->sidePowerSet(2, [sideDishes[0], [sideDishes[1]])

//->sidePowerSet(3, []);
//->sidePowerSet(3, [sideDishes[1]])
//->sidePowerSet(3, [sideDishes[0], [sideDishes[1]])
//->sidePowerSet(3, [sideDishes[2]);
//->sidePowerSet(3, [sideDishes[1], [sideDishes[2]])
//->sidePowerSet(3, [sideDishes[0], [sideDishes[1], [sideDishes[2]])

  // 결과를 사전식 순서로 정렬합니다.
  return result.sort();
}