-
https://programmers.co.kr/learn/courses/30/lessons/72412
못품. 조건별로 Map을 구현하고 조건끼리 연결이된, 마치 링크드 맵을 구현하려고 했는데, query문을 어떻게 처리해야 할지 몰라서 포기함.
그래서 다른 사람들의 풀이를 분석해봄.
첫 번째 풀이
지원자의 정보의 조합을 모두 키로 등록함. 지원자 한명의 정보는 총 (1 + 4 + 6 + 4) 개의 키로 등록이 됨.
가령,
"java backend junior pizza 150" 는
"- backend junior pizza 150" / "- - junior pizza 150" / "- - - pizza 150" / "- - - - 150" / " java - junior pizza 150" 등등등 으로 쪼개짐
두 번째 풀이
첫 번째 풀이와 유사하게 지원자 조건을 '분류 가능한 선'에서 전부 또는 일부로 압축된 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 내부로 가져가서 실행해보자. (딱히 수정은 안해놓겠다.)
'알고리즘 > 프로그래머스' 카테고리의 다른 글
다리를 지나는 트럭 (0) 2021.07.15 [Lv2] 수식 최대화 (0) 2021.07.01 [Lv2] 배달 (0) 2021.06.26 [Lv2] 124 나라 숫자 (0) 2021.06.21 [Lv3] 입국심사 (0) 2021.06.16 댓글