Programmers 21kakao_blind Ranking Search (Python)
This post was migrated from Tistory. You can find the original here.
https://school.programmers.co.kr/learn/courses/30/lessons/72412
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from bisect import bisect_left
def solution(info, query):
a = {"java":"0", "cpp":"1", "python":"2"}
b = {"backend":"0", "frontend":"1"}
c = {"junior":"0", "senior":"1"}
d = {"chicken":"0", "pizza":"1"}
results = []
for i in info:
lang, posi, car, food, score = i.split(" ")
results.append([a[lang], b[posi], c[car], d[food], int(score)])
r = {}
for result in results:
_d = "".join(result[:4])
if (r.get(_d)):
r[_d].append(result[4])
else:
r[_d] = [result[4]];
answer = []
s_dp = {}
for __i in r.keys():
s_dp[__i] = False
for q in query:
lang, posi, car, f = q.split(" and ")
food, score = f.split(" ")
u1 = []; u2 = []; u3 = []; u4 = []
if (lang == "-"):
u1.append("0"); u1.append("1"); u1.append("2");
else:
u1.append(a[lang])
if (posi == "-"):
u2.append("0"); u2.append("1");
else:
u2.append(b[posi])
if (car == "-"):
u3.append("0"); u3.append("1");
else:
u3.append(c[car])
if (food == "-"):
u4.append("0"); u4.append("1");
else:
u4.append(d[food])
count = 0
for _u1 in u1:
for _u2 in u2:
for _u3 in u3:
for _u4 in u4:
s = _u1 +_u2 + _u3 + _u4
if r.get(s):
arr = r[s]
if not s_dp[s]:
arr.sort()
s_dp[s] = True
f = bisect_left(arr,int(score))
count += len(arr) - f
answer.append(count)
return answer
Approach
java backend junior pizza = “0001”
python frontend senior chicken = “2110”
While iterating through info, build a dictionary like the following.
{“0001” : [150, 200], “2110” : [80] …. }
Then iterate through query, converting each entry into a string (e.g. “0001”),
use that string as a key to look up the sorted score list in the dictionary, and run a binary search to count the scores that are higher than or equal to the target.
A wildcard like “0-01” expands into every possible combination, e.g. [“0001”, “0101”].
The score list for a given key is sorted only the first time it’s accessed, and a DP flag is used so it isn’t re-sorted on subsequent lookups.