2021 카카오 신입 공채 1차 온라인 코딩테스트 (조합, 이진탐색)

https://school.programmers.co.kr/learn/courses/30/lessons/72411

프로그래머스

메뉴 리뉴얼

 

풀이(***)

주문한 메뉴 (ABCDE)에 대해서 조합을 만든다.

2번 이상 주문된 조합을 필터링한다.

메뉴 갯수가 같은 코스끼리 비교하여 가장 많은 주문 횟수를 가진 코스를 반환한다.

 

function solution(orders, course) {
  const combination = {};

  const getCombination = (order, current, pick) => {
    // 더 이상 선택할 수 있는 문자가 없으면 반환
    if (pick === 0) {
      const sortedOrder = current.split("").sort().join("");

      combination[sortedOrder] = (combination[sortedOrder] || 0) + 1;
      return;
    }

    for (let i = 0; i < order.length; i++) {
      // order.slice()를 통해 남아 있는 문자에 대해서 조합 진행
      getCombination(order.slice(i + 1), current + order[i], pick - 1);
    }
    // ""으로부터 시작하여 ""+A, ""+B, ""+C, ""+D, ""+E 처럼 하나씩 가져와서 조합을 만들어 나간다.
    // current ex) ""+A  :  i=1-[A], i=2-[AB, AC, AD, AE], i=3-[ABC, ABD, ABE, ACD, ACE, ADE], i=4-...
    // pick 만큼 선택되었으면 결과를 반환한다.
  };

  // 모든 주문에 대해 조합 생성
  orders.forEach((order) => {
    course.forEach((pick) => {
      getCombination(order, "", 2);
    });
  });

  // 2번 이상 주문된 조합을 필터링하고 정렬
  const filteredList = Object.entries(combination)
    .filter((item) => item[1] >= 2)
    .sort((a, b) => b[1] - a[1]);

  // 같은 메뉴 갯수별로 최대 주문횟수를 가진 조합들을 담기
  let result = [];

  course.forEach((pick) => {
    // 최대 주문횟수
    let maxOrderCount = 0;

    filteredList.forEach((item) => {
      const [menus, orderCount] = item;

      // 같은 메뉴 구성끼리만 비교
      if (menus.length === pick) {
        maxOrderCount = Math.max(maxOrderCount, orderCount);

        // 최대 주문 횟수인 조합일 경우 결과에 추가
        if (orderCount === maxOrderCount) {
          result.push(menus);
        }
      }
    });
  });

  return result.sort(); // 결과 정렬하여 반환
}

solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2, 3, 4]);

---

https://school.programmers.co.kr/learn/courses/30/lessons/72412

프로그래머스

순위 검색

 

우선 완전탐색으로 구현을 해보면 아래의 조건에 의해 무수히 많은 반복을 하게 된다.

- info 배열의 크기는 1 이상 50,000 이하입니다.
- 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
- query 배열의 크기는 1 이상 100,000 이하입니다.

 

풀이

https://mine-it-record.tistory.com/521

[프로그래머스] 순위 검색(LV.2) by javascript - 2021 KAKAO BLIND RECRUITMENT

 

지원자의 점수를 하나하나 탐색하면 끝도 없기 때문에

 

이진탐색을 이용하여 점수를 최저점으로 만족하는 지원자의 index를 찾아,

그 이상의 점수를 지닌 지원자를 한 번에 count하는 방식으로 효율적인 구현이 가능하다.

 

  const candidates = new Map();

  infos.forEach((info) => {

    let key = info.split(" ");

    const value = Number(key.pop());

    key = key.join("");

    candidates.set(key, candidates.get(key) ? [...candidates.get(key), value] : [value]);

  });

동일한 자격을 지닌 지원자의 답변과 점수리스트를 Map객체로 만든다.

Map(5) {
  'javabackendjuniorpizza' => [ 150 ],
  'pythonfrontendseniorchicken' => [ 210, 150 ],
  'cppbackendseniorpizza' => [ 260 ],
  'javabackendjuniorchicken' => [ 80 ],
  'pythonbackendseniorchicken' => [ 50 ]
}

 

 

  candidates.forEach((value, key) => {

    candidates.set(

      key,

      value.sort((a, b) => a - b)

    );

  });

이진탐색을 적용하려면 정렬이 필요하다. 점수를 오름차순 정렬한다.

  'pythonfrontendseniorchicken' => [ 150, 210 ],

 

 

  const result = [];

  // 자격 판별

  queries.forEach((query) => {

    const requirements = query.split(" ").filter((item) => item !== "-" && item !== "and");

    const score = Number(requirements.pop());

    // requirements를 만족하는 지원자 필터링

    const requireFiltered = Array.from(candidates).filter((candidate) =>

      requirements.every((require) => candidate[0].includes(require))

    );

  });

  return result;

}

query에 대해 조건을 만족하는 지원자를 걸러낸다.

includes() 메서드를 이용하여 자격조건을 'pythonfrontendseniorchicken' 이 문자열이 포함하고 있으면 된다.

 

 

    // requirements를 만족하는 지원자 중에서 score를 만족하는 지원자 카운트

    const scoreFulfilCount = requireFiltered

      .map((item) => {

        const targetScoreIndex = binarySearch(item[1], score);

        const scores = item[1].length;

        return scores - targetScoreIndex;

      })

      .reduce((total, score) => total + score, 0);

    result.push(scoreFulfilCount);

점수 무더기를 분류하기 위해서 이진탐색을 이용할 차례다.

점수를 만족하는 지원자 중 최저 점수를 지닌 점수의 인덱스를 찾고, 해당 인덱스보다 큰 지원자는 모두 카운트한다.

 

const binarySearch = (array, score) => {

  let left = 0;

  let right = array.length;

  while (left < right) {

    // 가운데 인덱스 설정

    const middle = Math.floor((left + right) / 2);

    if (array[middle] >= score) {

      // middle이 score보다 클 결우 right를 절반으로

      right = middle;

    } else {

      // middle이 score보다 작을 경우 left를 절반으로

      left = middle + 1;

    }

  }

이진탐색은 이해하는 것도 매우 쉽고 간단해보이지만

+1을 할지 -1을 할지, <, >, <=, >= 중에서 뭐를 골라야 할지 헷갈리기 쉽다. 

 

그래서 const sample = Array.from({ length: 20 }, (_,index) => index*2)

// [  0,  2,  4,  6,  8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38 ] 

 

이렇게 테스트용 배열을 만들어 의도대로 작동하는지 여러차례 확인과정을 거쳐야 했다.

 

 

function solution(infos, queries) {
  // condition을 key로, 점수를 value로 하는 맵 생성
  const candidates = new Map();

  infos.forEach((info) => {
    let key = info.split(" ");
    const value = Number(key.pop());
    key = key.join("");

    candidates.set(key, candidates.get(key) ? [...candidates.get(key), value] : [value]);
  });

  // 점수에 이진 탐색을 적용하기 위해서 점수를 내림차순으로 정렬
  candidates.forEach((value, key) => {
    candidates.set(
      key,
      value.sort((a, b) => a - b)
    );
  });

  const result = [];
  // 자격 판별
  queries.forEach((query) => {
    const requirements = query.split(" ").filter((item) => item !== "-" && item !== "and");
    const score = Number(requirements.pop());

    // requirements를 만족하는 지원자 필터링
    const requireFiltered = Array.from(candidates).filter((candidate) =>
      requirements.every((require) => candidate[0].includes(require))
    );

    // requirements를 만족하는 지원자 중에서 score를 만족하는 지원자 카운트
    const scoreFulfilCount = requireFiltered
      .map((item) => {
        const targetScoreIndex = binarySearch(item[1], score);
        const scores = item[1].length;
        return scores - targetScoreIndex;
      })
      .reduce((total, score) => total + score, 0);

    result.push(scoreFulfilCount);
  });

  return result;
}

const binarySearch = (array, score) => {
  let left = 0;
  let right = array.length;

  while (left < right) {
    // 가운데 인덱스 설정
    const middle = Math.floor((left + right) / 2);

    if (array[middle] >= score) {
      // middle이 score보다 클 결우 right를 절반으로
      right = middle;
    } else {
      // middle이 score보다 작을 경우 left를 절반으로
      left = middle + 1;
    }
  }

  return left;
};

---