프로그래머스[Level 2] 순위 검색

문제

링크

입출력 예

풀이

완전 탐색으로 풀어 테스트케이스 다 맞췄지만 효율성 테스트를 통과하지 못했다. 다시 확인해보니 문제의 시작에 효율성 테스트의 존재를 명시했고, 제한사항에 입력의 크기도 명시했기에 이대로 풀면 통과 못할 것은 제출 안해봐도 알 수 있었을 것이다. 문제를 좀 더 자세히 읽도록 하자.

그럼 어떻게 해결 할 수 있을까.

"java backend junior pizza 150" 이 지원자를 살펴보자 이 지원자는

java backend junior pizza 150

- backend junior pizza 150

java - junior pizza 150

java backend - pizza 150

java backend junior - 150

...

– – – – 150

이런 여러가지 부분에서 통과 할 수 있다.

카카오 기술 블로그를 참고하면, 총 16까지의 그룹에 속할 수 있다고 한다. 링크

지원자 정보를 저런식으로 모두 나눠서 객체로 저장을 한다.

'-'넣을 수 있는 부분에 넣고 조합으로 모두 찾고 문자열로 만들어 key값으로 하고 점수를 value로 넣는 객체로 만든다.
이 때, 키가 같은 경우가 생긴다. 따라서 value에는 배열로 값을 넣는다. 그리고 후에 이진탐색을 이용하여 값의 idx를 찾을 것이기 때문에 오름차순으로 정렬해준다.

객체를 완성하면

{
  javabackendjuniorpizza: [ '150' ],
  '-backendjuniorpizza': [ '150' ],
  '--juniorpizza': [ '150' ],
  '---pizza': [ '150', '260' ],
  '----': [ '50', '80', '150', '150', '210', '260' ],
  '--junior-': [ '80', '150' ],
  '-backend-pizza': [ '150', '260' ],
  '-backend--': [ '50', '80', '150', '260' ],
  '-backendjunior-': [ '80', '150' ],
  'java-juniorpizza': [ '150' ],
  'java--pizza': [ '150' ],
  'java---': [ '80', '150' ],
  'java-junior-': [ '80', '150' ],
  'javabackend-pizza': [ '150' ],
  'javabackend--': [ '80', '150' ],
  'javabackendjunior-': [ '80', '150' ],
  pythonfrontendseniorchicken: [ '150', '210' ],
  '-frontendseniorchicken': [ '150', '210' ],
  '--seniorchicken': [ '50', '150', '210' ],
  '---chicken': [ '50', '80', '150', '210' ],
  '--senior-': [ '50', '150', '210', '260' ],
  '-frontend-chicken': [ '150', '210' ],
  '-frontend--': [ '150', '210' ],
  '-frontendsenior-': [ '150', '210' ],
  'python-seniorchicken': [ '50', '150', '210' ],
  'python--chicken': [ '50', '150', '210' ],
  'python---': [ '50', '150', '210' ],
  'python-senior-': [ '50', '150', '210' ],
  'pythonfrontend-chicken': [ '150', '210' ],
  'pythonfrontend--': [ '150', '210' ],
  'pythonfrontendsenior-': [ '150', '210' ],
  cppbackendseniorpizza: [ '260' ],
  '-backendseniorpizza': [ '260' ],
  '--seniorpizza': [ '260' ],
  '-backendsenior-': [ '50', '260' ],
  'cpp-seniorpizza': [ '260' ],
  'cpp--pizza': [ '260' ],
  'cpp---': [ '260' ],
  'cpp-senior-': [ '260' ],
  'cppbackend-pizza': [ '260' ],
  'cppbackend--': [ '260' ],
  'cppbackendsenior-': [ '260' ],
  javabackendjuniorchicken: [ '80' ],
  '-backendjuniorchicken': [ '80' ],
  '--juniorchicken': [ '80' ],
  '-backend-chicken': [ '50', '80' ],
  'java-juniorchicken': [ '80' ],
  'java--chicken': [ '80' ],
  'javabackend-chicken': [ '80' ],
  pythonbackendseniorchicken: [ '50' ],
  '-backendseniorchicken': [ '50' ],
  'pythonbackend-chicken': [ '50' ],
  'pythonbackend--': [ '50' ],
  'pythonbackendsenior-': [ '50' ]
}

이렇게 된다.

이제 기준(querys)도 문자열로 바꿔서 객체안에서 만족하는 갯수를 찾으면 된다.

"- and - and - and - 150" 이런 입력이 들어온다면,
키가 "---" 이고 점수가 150점이 된다.

'----': [ '50', '80', '150', '150', '210', '260' ],

여기서 150점 이상인 개수를 찾으면 된다. 즉 4명이다.

const solution = (info, query) => {
  const answer = [];
  const map = {};

  const combination = (infos, score, map, start) => {
    const key = infos.join("");
    const value = map[key];
    // key, value의 생성
    if (value) {
      map[key].push(score);
    } else {
      map[key] = [score];
    }

    // 조합
    for (let i = start; i < infos.length; i++) {
      let combiArr = [...infos];
      combiArr[i] = "-";
      combination(combiArr, score, map, i + 1);
    }
  };

  // 이진탐색
  const binarySearch = (map, key, target) => {
    const scoreArr = map[key];

    if (scoreArr) {
      let start = 0;
      let end = scoreArr.length;

      while (start < end) {
        let mid = Math.floor((start + end) / 2);

        if (scoreArr[mid] >= target) {
          end = mid;
        } else if (scoreArr[mid] < target) {
          start = mid + 1;
        }
      }
      // 이진 탐색이 끝나고 start는 target 이하인 마지막 인덱스를 가르킨다.
      // 구하고 싶은 것은 더 큰 값의 개수이기에 length에서 start를 뺀다.
      return scoreArr.length - start;
    } else return 0;
  };

  for (let i = 0; i < info.length; i++) {
    let infos = info[i].split(" ");
    let score = infos.pop();
    combination(infos, score, map, 0);
  }

  // 이진 탐색을 위해 점수를 오름 차순으로 정리
  for (let key in map) {
    map[key].sort((a, b) => a - b);
  }

  console.log(map);
  for (let i = 0; i < query.length; i++) {
    let querys = query[i].replace(/ and /g, "").split(" ");
    let score = +querys.pop();
    answer.push(binarySearch(map, querys.join(""), score));
  }

  return answer;
};

복습

const solution = (info, query) => {
  const answer = [];
  const obj = {};

  const combination = (infoArr, obj, score, start) => {
    const key = infoArr.join("");
    const value = obj[key];

    if (value) {
      obj[key].push(score);
    } else {
      obj[key] = [score];
    }

    for (let i = start; i < infoArr.length; i++) {
      const restArr = [...infoArr];
      restArr[i] = "-";
      combination(restArr, obj, score, start + 1);
    }
  };

  const binarySearch = (obj, key, target) => {
    const scoreArr = obj[key];
    if (scoreArr) {
      let start = 0;
      let end = scoreArr.length;

      while (start < end) {
        let mid = Math.floor((start + end) / 2);

        if (scoreArr[mid] >= target) {
          end = mid;
        } else {
          start = mid + 1;
        }
      }
      return scoreArr.length - start;
    }
    return 0;
  };
  for (let i = 0; i < info.length; i++) {
    const infoArr = info[i].split(" ");
    const score = +infoArr.pop();
    combination(infoArr, obj, score, 0);
  }

  for (let key in obj) {
    obj[key].sort((a, b) => a - b);
  }

  for (let i = 0; i < query.length; i++) {
    const queryArr = query[i].replace(/ and /g, "").split(" ");
    const score = queryArr.pop();
    answer.push(binarySearch(obj, queryArr.join(""), score));
  }
  return answer;
};