[프로그래머스] 2021 KAKAO BLIND RECRUITMENT - "메뉴 리뉴얼" (Javascript)

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

코딩테스트 연습 - 메뉴 리뉴얼

---

 

난이도 :  Level 2

 

 적절한 자료구조를 활용할 줄 알아야하고 조합 구현 방법과 몇 가지 예외 처리가 존재하는 문제입니다. Level 2 난이도 치고는 요구하는 조건이 많은 문제라고 생각합니다. 

 

 제가 생각한 로직은 다음과 같습니다. 

1.  각 course의 사이즈 별로 Map 자료 구조를 생성하여 조합을 통해 모든 세트의 경우의 수를 key 값으로 설정하고 해당 key 값의 노출 횟수를 value로 설정하였습니다. 

2. Map의 value중 가장 큰 값을 찾아서 그 값과 일치하는 key 값을 answer 배열에 넣어주었습니다. 

3. sort() 함수를 통하여 사전순으로 정렬하여 답을 도출하였습니다. 

 

 

- solution(orders, course)

 기본 입력을 받고 정답을 도출합니다. course별로 Map을  설정해주기 위해 반복문을 탐색하고 세트 조합을 구하기 위해 orders 배열을 탐색합니다.  최종 answer 배열은 sort() 함수를 사용하여 사전순으로 정렬한 후에 정답을 반환하였습니다. 

 

-  combination(n, map, order, r, str, start)

 size(n)를 기준으로 order 문자열을 재귀 호출하여 조합을 구현합니다. 그 후 nCr에서 r이 n에 값에 도달하면 Map 자료구조에 set합니다. 

 

 여기서 예외처리가 하나 있습니다. 문자열로 Map의 key 값을 정했습니다. 하지만 문자열 자체가 key 값이 되는 것이 아닌 조합의 구성(세트) 자체가 key 값이 되는 것이므로, 재귀 호출을 통하여 각 course의 size를 만나면 문자열을 새로 sort() 함수로 정렬하여 새로 key 값을 설정하였습니다. 즉, 문자열 변수 str에 AB가 들어오나 BA가 들어오나 key 값은 AB가 됩니다. 

 

- getMaxSet(map, answer)

 Map의 value중 가장 큰 값을 찾아서 그 값과 일치하는 key를 answer에 push합니다. 첫 번째 for of 문에서는 가장 큰 value 값을 max에 저장하고, 두 번째 for of 문에서는 max 값과 일치하는 key 값을 answer에 push합니다. 한 사람에게만 선택된 세트는 정답에 넣지 않는 조건이 있으므로, max 값이 1인 경우도 제외합니다.

 

 

  코드

// PM / KAKAO 2021 BLIND / Level 2 / 메뉴리뉴얼

function solution(orders, course) {
  let answer = [];

  for (let i = 0; i < course.length; i++) {
    const size = course[i];
    const map = new Map();

    for (let j = 0; j < orders.length; j++) {
      const order = orders[j];
      combination(size, map, order, 0, '', 0);
    }
    getMaxSet(map, answer);
  }

  answer = answer.sort();
  return answer;
}

function getMaxSet(map, answer) {

  let max = 0;
  for (let value of map.values()) {
    if (max < value) {
      max = value;
    }
  }

  for (let [key, value] of map) {
    if (max === value && max !== 1) {
      answer.push(key);
    }
  }
}

function combination(n, map, order, r, str, start) {

  if (r == n) {
    let charArray = str.split('');
    charArray = charArray.sort();
    const key = charArray.join('');
    
    if (map.has(key)) {
      const value = Number(map.get(key));
      map.set(key, value + 1);
    } else {
      map.set(key, 1);
    }
    return;
  }

  for (let i = start; i < order.length; i++) {
    const ch = order.charAt(i);
    combination(n, map, order, r + 1, str + ch, i + 1);
  }
}

 

피드백 환영합니다.