프로그래머스 고득점 Kit 완전탐색

프로그래머스 고득점 Kit https://school.programmers.co.kr/learn/courses/30/parts/12230

프로그래머스

---

Level 1. 최소 직사각형

문제 요약

다양한 사이즈의 카드를 모두 넣을 수 있는 지갑을 만들려고 한다.

만들 수 있는 가장 작은 지갑 사이즈의 가로*세로의 값을 구하시오.

 

풀이
1. 전체 요소 중 가장 큰 값을 찾는다.

2. 가로 세로 중 작은 요소 중 가장 큰 값을 찾는다.

3. 1과 2를 곱한 값을 반환한다.

 

const solution = (card) => {

  let walletWidth = 0,

    walletHeight = 0;

  card.forEach((el) => {

    const [cardWidth, cardHeight] = el;

    if (walletWidth < Math.max(cardWidth, cardHeight)) walletWidth = Math.max(cardWidth, cardHeight);

    if (walletHeight < Math.min(cardWidth, cardHeight)) walletHeight = Math.min(cardWidth, cardHeight);

  });

  return walletWidth * walletHeight;

};

 

---

Level 1. 모의고사

문제 요약

정답 배열이 주어집니다. [1,2,3,4,5]

세 명의 학생이 자기만의 규칙을 가지고 정답을 찍습니다.

가장 많은 정답을 맞춘 사람의 번호를 담은 배열을 반환하세요.

중복이 될 경우엔 오름차순으로 모두 반환합니다.

 

풀이

1. 규칙에 따라 정답 갯수를 세립니다.

2. 가장 높은 점수를 가진 사람의 index를 반환합니다.

 

function solution(answers) {

  var result = [0, 0, 0];

  const a = [1, 2, 3, 4, 5];

  const b = [2, 1, 2, 3, 2, 4, 2, 5];

  const c = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

  answers.forEach((answer, index) => {

    if (answer === a[index % a.length]) result[0] += 1;

    if (answer === b[index % b.length]) result[1] += 1;

    if (answer === c[index % c.length]) result[2] += 1;

  });

  const winner = [];

  const highScore = Math.max(...result);

  result.forEach((score, index) => {

    if (score === highScore) winner.push(index + 1);

  });

  return winner;

}

 

---

Level 2. 소수 찾기

문제 요약

"011"과 같이 일련의 숫자를 나열한 문자열이 주어집니다.

문자열의 길이는 7 이하입니다.

각 숫자를 조합하여 만들 수 있는 수들 중 소수의 개수를 반환하세요.

 

 

function solution(numbers) {

  const isPrime = (number) => {

    if (number === 2) {

      return true;

    }

    if (number < 2 || number % 2 === 0) {

      return false;

    }

    for (let i = 3; i * i <= number; i += 2) {

      if (number % i === 0) {

        return false;

      }

    }

    return true;

  };

  const numberArray = numbers.split("");

  const foundPrimeSet = new Set();

 

  const permutation = (i, array, pick) => {

    if (i === pick) {

      const toCheckNumber = Number(array.slice(0, i).join(""));

      const isPrimeNumber = isPrime(toCheckNumber);

      if (isPrimeNumber) {

        return foundPrimeSet.add(toCheckNumber);

      }

    }

    for (let j = i; j < array.length; j++) {

      [array[i], array[j]] = [array[j], array[i]];

      permutation(i + 1, array, pick);

      [array[i], array[j]] = [array[j], array[i]];

    }

  };

 

  for (let pick = 1; pick <= numberArray.length; pick++) {

    permutation(0, numberArray, pick);

  }

  return foundPrimeSet.size;

}

 

 

풀이

1. 입력받은 숫자가 소수인지 판별하는 isPrime 함수를 만듭니다.

  const isPrime = (number) => {
    if (number === 2) {
      return true;
    }
    if (number < 2 || number % 2 === 0) {
      return false;
    }
    for (let i = 3; i * i <= number; i += 2) {
      if (number % i === 0) {
        return false;
      }
    }
    return true;
  };

 

2. 주어진 숫자 갯수 만큼의 조합을 구하는 함수를 만듭니다.

조합 중에서 소수인 수는 foundPrimeSet 에 추가합니다.

  const numberArray = numbers.split("");
  const foundPrimeSet = new Set();

  const permutation = (i, array, pick) => {
    if (i === pick) {
      const toCheckNumber = Number(array.slice(0, i).join(""));
      const isPrimeNumber = isPrime(toCheckNumber);
      if (isPrimeNumber) {
        return foundPrimeSet.add(toCheckNumber);
      }
    }
    for (let j = i; j < array.length; j++) {
      [array[i], array[j]] = [array[j], array[i]];
      permutation(i + 1, array, pick);
      [array[i], array[j]] = [array[j], array[i]];
    }
  };

 

3. 1개로 만들 수 있는 조합부터 문자열의 길이만큼의 조합을 모두 구합니다.

  for (let pick = 1; pick <= numberArray.length; pick++) {
    permutation(0, numberArray, pick);
  }​

4. foundPrimeSet의 size를 반환합니다.

  return foundPrimeSet.size;

---

Level 2. 카펫

문제 요약

갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

(항상 가로가 더 깁니다.)

 

문제 아이디어

// 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

// brown 모서리를 제외한다 - 4개
// (brown세로-2) * (brown가로-2)가 yellow가 된다

// yellow가
// 1개가 되려면 33
// 2개가 되려면 34 43
// 3개가 되려면 53 35
// 4개가 되려면 44 63
// 5개가 되려면 73
// 6개가 되려면 83 54 이 중에서 가로가 더 긴것

// => yellow를 구성할 수 있는 모든 곱셈 구하기 => 약수 구하기

문제 풀이

 

function solution(brown, yellow) {

  const divisor = [];

  // 약수 구하기

  for (let i = 0; i <= Math.sqrt(yellow); i++) {

    if (yellow % i === 0) {

      divisor.push(i);

      divisor.push(yellow / i);

    }

  }

  for (let i = 0; i < divisor.length; i += 2) {

    const column = divisor[i];

    const row = divisor[i + 1];

    if (column * 2 + row * 2 === brown - 4) {

      return [row + 2, column + 2];

    }

  }

}

 

 

1. yellow를 구성할 수 있는 값은 약수를 찾으면 된다.

  const divisor = [];
  // 약수 구하기
  for (let i = 0; i <= Math.sqrt(yellow); i++) {
    if (yellow % i === 0) {
      divisor.push(i);
      divisor.push(yellow / i);
    }
  }

2. 약수를 구하는 방법

 

예시) 25

 

나누었을 때 0이 되는 수는 25의 약수가 될 수 있다.

1*25 5*5 25*1 세가지의 방법이 있다.

 

3. 약수를 효율적으로 구하기

 

하지만 1부터 25까지 전부 수행할 필요가 없다.

25를 1로 나눠서 약수가 된다면,
반드시 25를 1로 나누어도 약수가 된다.

 

따라서 제곱근까지만 반복을 하여도 모든 약수를 구할 수 있다.

4. 약수의 곱이 brown - 4 (모서리 타일 제외) 를 이루는 값을 반환한다.

  for (let i = 0; i < divisor.length; i += 2) {
    const column = divisor[i];
    const row = divisor[i + 1];
    if (column * 2 + row * 2 === brown - 4) {
      return [row + 2, column + 2];
    }
  }

---

Level 2. 피로도

문제 요약

// 피로도는 0이상의 정수
// 던전입장조건: 최소 필요로 하는 피로도가 존재
// 던전입장 시: 소모하는 피로도가 존재
// ex) [70, 10] 던전입장 조건은 70 이상의 피로도가 남아야 하고, 입장 시에 10을 소모한다.

// 피로도가 최소필요도보다 높다면 => 해당 던전을 돌고 다음 던전을 탐색 => 끝날때까지 반복

// 모든 순열에 실행

 

탐색이 가능한 경우의 수를 구하는 방법 1

 

  const dfs = (i, array, result) => {

    if (i === array.length) {

      result.push([...array]);

      return;

    }

    for (let j = i; j < array.length; j++) {

      [array[i], array[j]] = [array[j], array[i]];

      dfs(i + 1, array, result);

      [array[i], array[j]] = [array[j], array[i]];

    }

  };

  const permutation = (array) => {

    const result = [];

    dfs(0, array, result);

    return result;

  };

  const dungeonPlans = permutation(dungeons);

 

배열의 자리를 하나씩 바꾸어가며 모든 순열을 만들 수 있는 경우의 수를 찾는다.

바꾼 자리를 되돌림으로써 불필요한 조합은 거르게 되어 효율을 높인다.

종료 조건은 배열의 길이만큼 시행하였을 때

 

탐색이 가능한 경우의 수를 구하는 방법 2

 

  const backtrack = (array, visitedArray, currentPermutation, result) => {

    if (currentPermutation.length === array.length) {

      result.push([...currentPermutation]);

      return;

    }

    for (let i = 0; i < array.length; i++) {

      if (!visitedArray[i]) {

        visitedArray[i] = true;

        currentPermutation.push(array[i]);

        backtrack(array, visitedArray, currentPermutation, result);

        currentPermutation.pop();

        visitedArray[i] = false;

      }

    }

  };

  const permutation= (array) => {

    const result = [];

    const visitedArray = Array(array.length).fill(false); // 방문 여부를 저장하는 배열

    backtrack(array, visitedArray, [], result);

    return result;

  };

  const dungeonPlans = permutation(dungeons);

 

아직 방문하지 않은 경우에는 배열에 추가하고 방문 표시를 한다.

종료 조건은 배열의 길이가 목표에 도달했을 때

 

순열에 대해 피로도 조건을 대입하여 가장 많은 탐색을 횟수를 반환한다.

 

function solution(k, dungeons) {

  const backtrack1 = (i, array, result) => {

    if (i === array.length) {

      result.push([...array]);

      return;

    }

 

    for (let j = i; j < array.length; j++) {

      [array[i], array[j]] = [array[j], array[i]];

      backtrack1(i + 1, array, result);

      [array[i], array[j]] = [array[j], array[i]];

    }

  };

  const permutation = (array) => {

    const result = [];

    backtrack1(0, array, result);

    return result;

  };

  const dungeonPlans = permutation(dungeons);

  let maximumDungeonCount = 0;

  for (let dungeonPlan of dungeonPlans) {

    let currentStamina = k;

    let dungeonTryCount = 0;

    for (let route of dungeonPlan) {

      const toEnterDungeonStamina = route[0];

      const usageStamina = route[1];

      if (currentStamina >= toEnterDungeonStamina) {

        currentStamina -= usageStamina;

        dungeonTryCount++;

      }

    }

    maximumDungeonCount = Math.max(maximumDungeonCount, dungeonTryCount);

  }

  return maximumDungeonCount;

}

 

---