Search

PGS 순위 검색

태그
이분 탐색
매개 변수 탐색
구현
생성일
2024/12/11 12:11

문제 설명

주어진 지원자 정보와 조건에 따라 특정 조건을 만족하며 코딩테스트 점수가 X점 이상인 지원자 수를 효율적으로 계산하는 도구를 구현하는 문제

예제 입력/출력

info
query
result
["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"]
["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]
[1,1,1,1,2,4]

제약 조건

1info50,0001 ≤ |info| ≤ 50,000
1query100,0001 ≤ |query| ≤ 100,000

문제 풀이

접근1 브루트 포스 - O(queryinfo5)O(|query| \cdot |info| \cdot 5)
접근2 딕셔너리(해쉬) + 파라매트릭 서치 - O(info+infologinfo+queryloginfo)O(|info| + |info| log|info| + |query| \cdot log |info|)

풀이 코드

접근2 딕셔너리(해쉬) + 파라매트릭 서치 - O(info+infologinfo+queryloginfo)O(|info| + |info| log|info| + |query| \cdot log |info|)

참고 자료