본문 바로가기

이분탐색2

[programmers][2021카카오공채] 순위 검색 문제 : https://programmers.co.kr/learn/courses/30/lessons/72412 query가 100,000 infos가 50,000. query 문자열에 맞게 infos에 맞는 조건을 찾아서 정답을 구하기엔 시간이 부족하다. 개발언어가 3개. 직군 2개. 경력 2개. 소울푸드 2개. 3x2x2x2 = 24개의 조합에 맞는 score들을 저장해두면 시간을 확 줄일 수있다. scores[개발언어][직군][경력][소울푸드] = 점수들 배열. 만약 query에 개발언어가 상관없다면 scores[0~3][직군][경력][소울푸드]의 scores 조건에 맞는 점수들의 수를 정답에 포함시킨다. query에 개발언어가 java라면 scores[java 인덱스][직군][경력][소울푸드]의 s.. 2021. 3. 6.
[leetcode][1014] Capacity To Ship Packages Within D Days 문제 : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/ 이분탐색으로 풀었다.l = weights 배열중 가장 작은 수. r = weights 배열의 합.정답이 될 수 있는 값의 제일 작은 값(l), 제일 큰 값(r)을 구하고 l을 증가, r을 감소 시키면서 정답이 될 수 있는 가장 작은 수를 구한다.l과 r의 중간값을 구한다음, 구한 중간 값으로 weights 배열을 탐색하면서 소요되는 day를 직접 구해본다.구한 day가 D보다 작거나 같다면 정답이 될 수 있는 경우이므로 r을 중간값으로 갱신한다음 다시 반복한다.day가 D보다 크다면 정답이 될 수 없으므로 l을 중간값+1으로 갱신 후 다시 반복한다.이를 l이 r보다 크거.. 2019. 3. 22.