🎯 Achievement Goals

• 코플릿 [순열] 발표 순서
• 코플릿 [조합] 블랙잭은 지겨워
• 코플릿 [GCD] 빼빼로 데이

👉 코플릿 [순열] 발표 순서

문제

말썽꾸러기 김코딩은 오늘도 장난을 치다가 조별 발표 순서가 담긴 통을 쏟고 말았습니다.

선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.

김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤, 선생님께서 숫자를 말하면 그 순서에 맞는 경우의 수를 말해야 하고, 발표 순서를 말하면 이 발표순서가 몇번째 경우의 수인지를 대답해야 합니다.

총 학생의 수 N과 선생님이 말하는 k가 주어질 때, 김코딩이 정답을 말 할 수 있게 올바른 리턴 값을 구하세요.

모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다. ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

주의사항

k가 Number 일 때, k번째 배열을 리턴합니다. ex) n이 3이고 k가 3일 경우

모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,

반환하는 값은 [2, 3, 1]이 됩니다.

k가 Array일 때, 몇 번째인지를 리턴합니다. (0 <= index 입니다.) ex) n이 3이고 k가 [2, 3, 1]일 경우

모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,

반환하는 값은 3이 됩니다.

• k내에 중복되는 요소는 없다고 가정합니다.

입출력 예시

let output = orderOfPresentation(3, 3);
console.log(output); // [2,3,1]

let output = orderOfPresentation(3, [2, 3, 1]);
console.log(output); // 3

code

function orderOfPresentation(n, k) {

  const permutator = (inputArr) => {
  let result = [];
  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }
 
  permute(inputArr)
  return result;
 }
  let arr = []
  for (let i = 1; i <= n; i++) {
    arr.push(i)
  }
  let result = permutator(arr)

  if(Array.isArray(k)) {
    return result.indexOfForArrays(k)
  }
  return result[k];
}

Array.prototype.indexOfForArrays = function(search) {
  let searchJson = JSON.stringify(search);
  let arrJson = this.map(JSON.stringify);
  return arrJson.indexOf(searchJson);
};

👉 코플릿 [조합] 블랙잭은 지겨워

문제

평범한 블랙잭 게임이 질린 김코딩은 박해커에게 게임룰을 변형하여 새로운 카드 놀이를 해 볼 것을 제안합니다. 새로운 룰은 다음과 같습니다.

카드를 여러장 받아 그 중 3장의 카드를 고르는데, 그 3장에 적힌 숫자의 합은 소수여야 한다. 받아든 카드로 만들 수 있는 소수의 개수는 몇 개인가?

주의사항

• cards 에는 중복된 숫자의 카드는 들어있지 않습니다.
• 각 카드에 적힌 수는 1이상 1,000이하의 자연수입니다.

입출력 예시

let output = boringBlackjack([1, 2, 3, 4]);
console.log(output); // 1

let output = boringBlackjack([2, 3, 4, 8, 13]);
console.log(output); // 3

🤔 나의 생각

• 각각 다른 세 장의 카드를 더해줘야 하기 때문에 카드 배열을 3중 포문으로 순회를 하면서 각각 i,j,k를 더해주었다.
• 더해주고 그 더한 값이 소수인지 아닌지를 판별해야 하기 때문에 소수 판별 함수를 만들어 주었다.
• 소수인지 확인이 되었으면 그 때, 카운트를 해준다.

code

function boringBlackjack(cards) {

    let count = 0;
    for (let i = 0; i < cards.length; i++) {
      for (let j = i+1; j < cards.length; j++) {
        for (let k = j+1; k < cards.length; k++) {
          if (check(cards[i] + cards[j] + cards[k])) {
            count++;
          }
        }
      }
    }
    return count;
}

}

// 소수 판별 함수
function isPrime (n) {
    let len = parseInt(Math.sqrt(n));

    for (let i = 2; i < len; i++) {
        if (n % i === 0) {
            return false;
        }
    }
    return true;
}

👉 코플릿 [GCD] 빼빼로 데이

문제

오늘은 빼빼로 데이입니다. 한 회사의 팀장은 출근길에 아몬드 빼빼로 A 개와 누드 빼빼로 N 개를 구매하여 아침 일찍 출근길에 나섰습니다.

팀장은 자신보다 먼저 출근해있는 직원들에게 빼빼로를 모두 나누어 주려고 합니다. 단, 직원들이 서로 같은 개수의 빼빼로를 받지 못하면 시기 질투할 수 있으므로 직원들에게 같은 개수를 나누어 주어야 하며, 한 가지 종류의 빼빼로만 받는 경우가 없어야 합니다.

회사에 도착하기 전이기 때문에 이미 출근해 있는 직원들이 몇 명인지 모르는 상황입니다. 예를 들어, 팀장이 아몬드 빼빼로를 4개, 누드 빼빼로를 8개를 구매 했다면, 다음과 같이 세 가지 방법으로 나누어 줄 수 있습니다.

• 출근한 직원이 1명이라면 아몬드 빼빼로 4개와 누드 빼빼로 8개를 줄 수 있습니다.
• 출근한 직원이 2명이라면 아몬드 빼빼로 2개와 누드 빼빼로 4개를 각각 줄 수 있습니다.
• 출근한 직원이 4명이라면 아몬드 빼빼로 1개와 누드 빼빼로 2개를 각각 줄 수 있습니다.
• 팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다.

여러분이 직원 수에 따라 빼빼로를 나누어 주는 방법을 구하는 솔루션을 제공해 주세요.

출력

• 직원 수에 따라 각각 빼빼로를 나누어 주는 방법을 다음과 같은 순서로 배열에 담아야 합니다.
• Number 타입의 요소
• [빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]
• 위와 같은 방법들을 순서에 상관없이 배열에 담아 출력해야 합니다.

입출력 예시

let A = 4;
let N = 8;

let output = divideChocolateStick(A, N);
console.log(output) 
// [[1, 4, 8], [4, 1, 2], [2, 2, 4]] 또는,
// [[1, 4, 8], [2, 2, 4], [4, 1, 2]] 
// 순서는 상관없습니다

🤔 나의 생각

• 먼저 최대 공약수 문제이기 때문에 유클리드 호제법을 활용해서 최대 공약수를 구해주는 함수를 만들어 준다.
• 약수는 제곱근을 기준으로 구할 수 있다.
• 반복문을 최대공약수의 제곱근까지 순회한다.
• 그러면서 i가 최대공약수와 나누어 떨어지면 약수로 간주하고 값을 저장한다.
• 반복문의 효율을 높이기 위해, 최대공약수와 i를 나눴을 때, i가 아니라면 제곱근이 아닌 경우.
• 이 때, 최대공약수를 제곱근이 아닌 수로 나눠주면 제곱근 보다 더 큰 약수를 구할 수 있다.

code

function divideChocolateStick(A, N) {
    let result = [];
    let check = gcd(Math.max(A, N), Math.min(A, N));
    let len = parseInt(Math.sqrt(check));

    for (let i = 1; i <= len; i++) {
        if (check % i === 0) {
            result.push(i, A / i, N / i);
            // 제곱근 보다 작은 수
            // 최대 공약수를 제곱근이 아닌 수로 나눠주면 제곱근 보다 큰 수를 구할 수 있다.
            if (i !== check / i) {
                let x = check / i;
                result.push(x, A / x, N / x)
            }
        }
    }
    return result;
}

// 유클리드 호제법
function gcd (maxNum, minNum) {
    return maxNum % minNum === 0 ? minNum : gcd(minNum, maxNum % minNum);
}

🙌 느낀점

오늘 풀었던 조합과 최대공약수 문제는 그럭저럭 할만 하다고 느꼈다. 그러나 순열은 아직도 많이 어렵다 ㅜㅜ 내일은 이머시브 온 뒤로 첫 H.A 테스트 시험을 보는 날이다. 이머시브에서는 3주마다 테스트 과정을 보는데 내 실력 체크를 할 수있는 기회라고 생각한다.

이번에는 알고리즘을 풀기 위한 자료구조를 공부했기 때문에, 알고리즘 위주로 H.A 시험문제가 나올 것으로 예상된다.

잘 풀렸으면 좋겠다..

👊 내일의 TIW(today I Will)

H.A 시험