プログラマー2021 KAKAO BLIND RECRUITMENTランキング
問題の説明が長すぎます.リンクを参照してください.
https://programmers.co.kr/learn/courses/30/lessons/72412
プール(効率ゼロ) def solution(_info, _query):
answer = []
infoList = list(map(lambda x: x.split(' '), _info))
queryList = list(map(lambda x: x.replace('and ', ''), _query))
queryList = list(map(lambda x: x.split(' '), queryList))
queryset = list([set([]) for _ in range(5)] for _ in range(len(queryList)))
for i, query in enumerate(queryList):
for j in range(len(query)):
for info in infoList:
if query[j].isdigit():
if int(query[j]) <= int(info[j]) or query[j] == '-':
queryset[i][j].add(' '.join(info))
else:
if query[j] == info[j] or query[j] == '-':
queryset[i][j].add(' '.join(info))
for q in queryset:
winning = q[0] & q[1] & q[2] & q[3] & q[4]
cnt = 0
for w in winning:
cnt += _info.count(w)
answer.append(cnt)
return answer
def solution(_info, _query):
answer = []
infoList = list(map(lambda x: x.split(' '), _info))
queryList = list(map(lambda x: x.replace('and ', ''), _query))
queryList = list(map(lambda x: x.split(' '), queryList))
queryset = list([set([]) for _ in range(5)] for _ in range(len(queryList)))
for i, query in enumerate(queryList):
for j in range(len(query)):
for info in infoList:
if query[j].isdigit():
if int(query[j]) <= int(info[j]) or query[j] == '-':
queryset[i][j].add(' '.join(info))
else:
if query[j] == info[j] or query[j] == '-':
queryset[i][j].add(' '.join(info))
for q in queryset:
winning = q[0] & q[1] & q[2] & q[3] & q[4]
cnt = 0
for w in winning:
cnt += _info.count(w)
answer.append(cnt)
return answer
inputとしてのinfoではsetのinfoが何個あるかを数えて、そのクエリを満たす人数を得ることができます.
他人を解く from itertools import combinations
def solution(info, query):
answer = []
db = {}
# 모든 경우의 수 만들기
for i in info:
temp = i.split(' ')
condition = temp[:-1]
score = int(temp[-1])
for n in range(5):
combi = list(combinations(range(4), n)) # (0,1,2,3) 중에서 n개 뽑기
for c in combi:
temp_con = condition[:]
for switch in c:
temp_con[switch] = '-'
key = ''.join(temp_con)
# 같은 것들 그룹화 해서 딕셔너리에 넣어 주기
if key in db:
db[key].append(score) # 문자열이 있으면 그 그룹에 점수 추가하고
else:
db[key] = [score] # 문자열이 없으면 그룹을 만들고 점수 추가
# 딕셔너리 모든 값들 그룹별로 정렬
for value in db.values():
value.sort()
for q in query:
# 쿼리 파싱
temp_q = q.replace('and ', '').split(' ')
q_condition = ''.join(temp_q[:-1])
q_score = int(temp_q[-1])
# 쿼리가 딕셔너리에 존재하면
if q_condition in db:
data = db[q_condition]
if len(data) > 0:
start, end = 0, len(data) # lower bound 알고리즘 통해 인덱스 찾고,
while start != end and start != len(data):
if data[(start + end) // 2] >= q_score:
end = (start + end) // 2
else:
start = (start + end) // 2 + 1
answer.append(len(data) - start) # 해당 인덱스부터 끝까지의 갯수가 정답
else:
answer.append(0)
return answer
まずinfoを条件と点数に分けます
任意の場合、コンビネーションを使用して作成できます.
ディック・シャナリーの身長単位で、点数を値に(グループ化)
例えばjava後端初級ピザ150であれば、
java/backend/junior/pizza
-/backend/junior/pizza
java/-/junior/pizza
{...}
-/-/-/pizza
-/-/-/-
このように16個の組み合わせを作り、鍵で置いておきます.
ベル類を採点して、この時グループを分けて、リストに並べます
その後、ディックシャナリーキー値に基づいてすべてのベルをソートします(バイナリナビゲーションのために)
クエリがディック郡に存在する場合
それらのデータを受け取る
バイナリ・ナビゲーション・アルゴリズムの1つです.下限アルゴリズムです.
最小値のインデックスを見つけます.
そのインデックスから、個数を答えに入れればいいのです.
ポイントはバイナリナビゲーションを使用することです.
値を検索するのではなく、その値以上の最小値を検索する必要があります.
下界アルゴリズムを用いて効率を向上させる.
正確性は容易な問題のようだが、効率性は難しすぎるようだ.
これはlvです.2;
Reference
この問題について(プログラマー2021 KAKAO BLIND RECRUITMENTランキング), 我々は、より多くの情報をここで見つけました
https://velog.io/@whanhee97/프로그래머스-2021-KAKAO-BLIND-RECRUITMENT-순위-검색
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
from itertools import combinations
def solution(info, query):
answer = []
db = {}
# 모든 경우의 수 만들기
for i in info:
temp = i.split(' ')
condition = temp[:-1]
score = int(temp[-1])
for n in range(5):
combi = list(combinations(range(4), n)) # (0,1,2,3) 중에서 n개 뽑기
for c in combi:
temp_con = condition[:]
for switch in c:
temp_con[switch] = '-'
key = ''.join(temp_con)
# 같은 것들 그룹화 해서 딕셔너리에 넣어 주기
if key in db:
db[key].append(score) # 문자열이 있으면 그 그룹에 점수 추가하고
else:
db[key] = [score] # 문자열이 없으면 그룹을 만들고 점수 추가
# 딕셔너리 모든 값들 그룹별로 정렬
for value in db.values():
value.sort()
for q in query:
# 쿼리 파싱
temp_q = q.replace('and ', '').split(' ')
q_condition = ''.join(temp_q[:-1])
q_score = int(temp_q[-1])
# 쿼리가 딕셔너리에 존재하면
if q_condition in db:
data = db[q_condition]
if len(data) > 0:
start, end = 0, len(data) # lower bound 알고리즘 통해 인덱스 찾고,
while start != end and start != len(data):
if data[(start + end) // 2] >= q_score:
end = (start + end) // 2
else:
start = (start + end) // 2 + 1
answer.append(len(data) - start) # 해당 인덱스부터 끝까지의 갯수가 정답
else:
answer.append(0)
return answer
Reference
この問題について(プログラマー2021 KAKAO BLIND RECRUITMENTランキング), 我々は、より多くの情報をここで見つけました https://velog.io/@whanhee97/프로그래머스-2021-KAKAO-BLIND-RECRUITMENT-순위-검색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol