[Lv2] 순위 검색

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

코딩테스트 연습 - 순위 검색

---

못품. 조건별로 Map을 구현하고 조건끼리 연결이된, 마치 링크드 맵을 구현하려고 했는데, query문을 어떻게 처리해야 할지 몰라서 포기함.

 

 

그래서 다른 사람들의 풀이를 분석해봄.

 

첫 번째 풀이

 

https://velog.io/@alvin/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%88%9C%EC%9C%84-%EA%B2%80%EC%83%89-Javascript

프로그래머스 문제풀이 - 순위 검색 (Javascript)

 

지원자의 정보의 조합을 모두 키로 등록함. 지원자 한명의 정보는 총 (1 + 4 + 6 + 4) 개의 키로 등록이 됨.

가령, 

 

"java backend junior pizza 150" 는

"- backend junior pizza 150" / "- - junior pizza 150" / "- - - pizza 150" / "- - - - 150" / " java - junior pizza 150" 등등등 으로 쪼개짐

 

두 번째 풀이

 

https://all-dev-kang.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-2021-KAKAO-BLIND-RECRUITMENT-%EC%88%9C%EC%9C%84-%EA%B2%80%EC%83%89-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8

[프로그래머스] 2021 KAKAO BLIND RECRUITMENT -> 순위 검색 - 자바스크립트

 

첫 번째 풀이와 유사하게 지원자 조건을 '분류 가능한 선'에서 전부 또는 일부로 압축된 key로 등록한다. 그렇기 때문에 나처럼 체이닝 맵 마냥 더듬더듬 찾아가면서 검색할 필요 없이, 압축된 key 있니? 하고 물어보면 답이 나오기 때문에, 효율성 면에서 더 나은 구현이 가능한가보다.

 

참고로 글쓴이가 코드 한줄에 대한 풀이를 잘못써놓은 것 같아서 적어보자면 toUpperCase를 넣어놓은 이유는, 좋아하는 음식이 chicken인 경우 첫 글자 c와, 프로그래밍 언어 cpp의 첫 글자가 같아서임. 구분하기 위해서 toUpperCase를 해준 듯 하다. 만약 조건이 추가돼서 c가 하나 더 들어올 수 있는 일이 발생한다면 다른 방안을 생각해봐야 겠지?

 

나름 위 두 코드의 아이디어를 합해서 아래와 같이 만들었는데, 효율성 테스트를 통과하지 못한다. 시간복잡도는 분석 중임...

 

function solution(info, query) {
    var answer = [];
    var applications = new Map();

    for (let i = 0; i < info.length; i++) {
        let application = info[i];
        application = application.split(' ');

        let score = application.pop();
        application = application.join('');

        if (!applications.has(application)) {
            applications.set(application, [+score]);
        } else {
            let pointArr = applications.get(application);
            pointArr.push(+score);
            applications.set(application, pointArr);
        }
    }

    for (let i = 0; i < query.length; i++) {
        let condition = query[i].replace(/and /g, '').replace(/- /g, '').split(' ');
        let requiredScore = +condition.pop();
        let satisfiedPeoples = 0;
        let satisfied = [];

        for (let [application, scores] of applications) {
            let pass = true;
            for (let j = 0; j < condition.length; j++) {
                if (!application.includes(condition[j])) {
                    pass = false;
                    break;
                }
            }

            if (pass) {
                satisfiedPeoples += binarySearch(requiredScore, applications.get(application));
            }
        }

        answer.push(satisfiedPeoples);
    }

    return answer;
}

function binarySearch(targetScore, arr) {
    let left = 0;
    let right = arr.length;

    arr.sort((a, b) => {
        return a - b;
    });

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

        if (arr[mid] >= targetScore) {
            right = mid;
        } else if (arr[mid] < targetScore) {
            left = mid + 1;
        }
    }

    return arr.length - left;
}

 

문제는 특정 key를 방문할 때마다 sort하는 것 -_-...

 

첫 번째 코드에 비해서 분명 시간복잡도가 불리한게 아닌데 하고 찾아보니... satisfied 배열을 방문할 때마다 sort를 해서 효율성 테스트를 통과하지 못했다. 

 

binarySearch 함수에 있는 sort함수만 solution 내부로 가져가서 실행해보자. (딱히 수정은 안해놓겠다.)