문제
https://school.programmers.co.kr/learn/courses/30/lessons/72412
소스코드
import collections
def solution(info, query):
#infomap[key]에 값을 추가해줍니다.
infomap = collections.defaultdict(list)
# 지원자의 정보로 가능한 모든 조합의 키를 생성
for inf in info:
a, b, c, d, p = inf.split()
for l in [a, '-']:
for m in [b, '-']:
for n in [c, '-']:
for o in [d, '-']:
infomap[l+m+n+o].append(int(p))
#이분탐색을 위해 infomap의 값들을 정렬합니다.
for k in infomap:
infomap[k].sort()
# 이분탐색으로 point 이상의 값 개수를 구합니다.(효율성)
answers = []
for q in query:
l, _, p, _, c, _, f, point = q.split()
score_list = infomap[l + p + c + f]
l,r = 0,len(score_list)
while l < r:
mid = (l+r) //2
if score_list[mid] >= int(point):
r = mid
else:
l = mid+1
answers.append(len(score_list) - l)
return(answers)설명
사용자 정보인 문자열을 쪼개서 key로 만들고 점수를 value로 한 딕셔너리를 만들어준다.
이때 단순히 사용자의 정보만 가지고 입력을 받으면 '-' 조건을 맞출 수 없다. 그래서 사용자 조건이 있을 때 가능한 모든 경우의 수를 key로 만들어서 같은 점수를 줘야한다.
만약 java backend junior pizza 150 이라고 주어지면 - backend junior pizza 이란 조건도 150 점이다. 왜냐면 언어가 상관없는 경우도 150점에 해당하기 때문이다 (예외조건)
점수를 key에 놓고 오름차순 정렬을 해준다.
효율성 검사에 통과하기 위해 이분탐색을 통해 n점 이상 받은 사람은 몇명인지 찾아줘야한다.
n점인 경우가 처음 나오는 인덱스가 몇번 인덱스인지 찾아내면 된다.
만약 value값이 [10,20,50,50,150] 일 때 50점 이상인 사람이 몇명인지 찾으려면 전체 5개에서 (50이 처음나오는 인덱스 인) 2를 빼주면 된다. 그래서 50이 넘는 점수는 총 3개이다.
이를 위해서 이분탐색을 진행할 때 l < r , 범위를 좁힐 때 l = mid + 1 , r = mid 을 써줘야한다.
[10,20,50,50,150]일 때 50이 나오는 첫번째 인덱스를 찾아보자
# 1
l = 0, r = 5, mid = 2, if 조건 충족 r = 2로 변경# 2
l = 0, r = 2, mid = 1, if 조건 충족 안함 l = 2 로 변경# 3
l = 2, r = 2 이기 때문에 while 문 탈출
