프로그래머스 LEVEL 2(순위 검색)

사용 언어 : javascript
해결 날짜 : 2023-05-09
해결 방법 :
- 이분탐색을 통해 문제 해결
  - info를 돌며 지원자의 ${language}${group}${career}${soulFood}를 key값으로 score를 map에 set
    - 이 때, 중복 key값을 고려하여 value는 배열 형태
  - 저장된 map을 돌며 value 배열을 오름차순 정렬
  - query를 돌며
    - query로 만들 수 있는 모든 key 구하기(queryToKeys)
    - 구한 keys를 돌며 key마다 이분탐색 수행

회고 :

처음에 작성한 코드

const LANGUAGES = ['cpp', 'java', 'python'],
  GROUPS = ['backend', 'frontend'],
  CAREERS = ['junior', 'senior'],
  SOULFOODS = ['chicken', 'pizza'];

const queryToKeys = (language, group, career, soulFood) => {
  const languages = [language],
    groups = [group],
    careers = [career],
    soulFoods = [soulFood];

  if (language === '-') {
    languages.pop();
    LANGUAGES.forEach((LANGUAGE) => languages.push(LANGUAGE));
  }
  if (group === '-') {
    groups.pop();
    GROUPS.forEach((GROUP) => groups.push(GROUP));
  }
  if (career === '-') {
    careers.pop();
    CAREERS.forEach((CAREER) => careers.push(CAREER));
  }
  if (soulFood === '-') {
    soulFoods.pop();
    SOULFOODS.forEach((SOULFOOD) => soulFoods.push(SOULFOOD));
  }

  const keys = [];

  languages.forEach((language) => {
    groups.forEach((group) => {
      careers.forEach((career) => {
        soulFoods.forEach((soulFood) => {
          keys.push(`${language}${group}${career}${soulFood}`);
        });
      });
    });
  });

  return keys;
};

function solution(info, query) {
  const map = new Map();

  info.forEach((v) => {
    const [language, group, career, soulFood, score] = v.split(' ');

    map.set(
      `${language}${group}${career}${soulFood}`,
      map.has(`${language}${group}${career}${soulFood}`)
        ? [...map.get(`${language}${group}${career}${soulFood}`), +score]
        : [+score],
    );
  });

  return query.map((q) => {
    const [language, group, career, soulFood, score] = q.replaceAll('and ', '').split(' ');

    const keys = queryToKeys(language, group, career, soulFood);

    return keys
      .filter((key) => map.has(key))
      .map((key) => map.get(key).filter((s) => s >= score).length)
      .reduce((acc, cur) => acc + cur, 0);
  });
}

정확성 테스트는 전부 통과했으나, 효율성 테스트에서 전부 실패했다…
query를 key로 변환 후 map에서 key의 값들 중 score 이상인 값을 filtering하는 과정에서 시간초과가 난 것 같으므로 해당 로직을 이분탐색으로 변경하였다.

이분탐색으로 변경한 코드

// return query.map((q) => {
//  const [language, group, career, soulFood, score] = q.replaceAll('and ', '').split(' ');
//
//  const keys = queryToKeys(language, group, career, soulFood);
//
//  return keys
//    .filter((key) => map.has(key))
//    .map((key) => map.get(key).filter((s) => s >= score).length)
//    .reduce((acc, cur) => acc + cur, 0);
// });

return query.map((q) => {
  const [language, group, career, soulFood, score] = q.replaceAll('and ', '').split(' ');

  const keys = queryToKeys(language, group, career, soulFood);

  let count = 0;

  keys.forEach((key) => {
    if (!map.has(key)) return;

    const scores = map.get(key);
    let left = 0,
      right = scores.length;

    while (left < right) {
      const mid = Math.floor((right + left) / 2);

      if (scores[mid] < score) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    count += scores.length - left;
  });

  return count;
});

통과 ~~!!

코드

const LANGUAGES = ['cpp', 'java', 'python'],
  GROUPS = ['backend', 'frontend'],
  CAREERS = ['junior', 'senior'],
  SOULFOODS = ['chicken', 'pizza'];

const queryToKeys = (language, group, career, soulFood) => {
  const languages = [language],
    groups = [group],
    careers = [career],
    soulFoods = [soulFood];

  if (language === '-') {
    languages.pop();
    LANGUAGES.forEach((LANGUAGE) => languages.push(LANGUAGE));
  }
  if (group === '-') {
    groups.pop();
    GROUPS.forEach((GROUP) => groups.push(GROUP));
  }
  if (career === '-') {
    careers.pop();
    CAREERS.forEach((CAREER) => careers.push(CAREER));
  }
  if (soulFood === '-') {
    soulFoods.pop();
    SOULFOODS.forEach((SOULFOOD) => soulFoods.push(SOULFOOD));
  }

  const keys = [];

  languages.forEach((language) => {
    groups.forEach((group) => {
      careers.forEach((career) => {
        soulFoods.forEach((soulFood) => {
          keys.push(`${language}${group}${career}${soulFood}`);
        });
      });
    });
  });

  return keys;
};

function solution(info, query) {
  const map = new Map();

  info.forEach((v) => {
    const [language, group, career, soulFood, score] = v.split(' ');

    map.set(
      `${language}${group}${career}${soulFood}`,
      map.has(`${language}${group}${career}${soulFood}`)
        ? [...map.get(`${language}${group}${career}${soulFood}`), +score]
        : [+score],
    );
  });

  map.forEach((value, key) => {
    map.set(
      key,
      map.get(key).sort((a, b) => a - b),
    );
  });

  return query.map((q) => {
    const [language, group, career, soulFood, score] = q.replaceAll('and ', '').split(' ');

    const keys = queryToKeys(language, group, career, soulFood);

    let count = 0;

    keys.forEach((key) => {
      if (!map.has(key)) return;

      const scores = map.get(key);
      let left = 0,
        right = scores.length;

      while (left < right) {
        const mid = Math.floor((right + left) / 2);

        if (scores[mid] < score) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }

      count += scores.length - left;
    });

    return count;
  });
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges