문제설명
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
COMENT & 풀이
처음엔 효율성이고 따지지않고 냅다 구현해서 안됐당. SET자료형으로 차집합으로 풀랬는데 안됐당. 📌시간 복잡도를 따지는 걸 좀 더 연습해야겠다. 딱 봤을 때 아 위 두 방식대로 풀면 조지겠구나를 알아야할텐뒈..
결국 이 문제는 ⭐해시 + 이분탐색 ⭐문제였따
1명의 지원자가 들어갈 수 있는 쿼리의 경우의 수는 16가지 밖에 안된다 -> 적은 수다 = 조합을 활용해서 16가지의 경우의 수를 딕셔너리 키로 저장, values를 점수로 저장해 진짜 쿼리문을 딕셔너리에 KEY값으로 검색하여 쿼리문을 찾는 시간 복잡도를 O(1)로 해주는 ✅해시 알고리즘을 사용한다.
진짜 쿼리문이 딕셔너리 키값으로 존재한다면 점수값을 비교해야한다. 딕셔너리를 만든 후 값들을 모두 정렬해놓고 쿼리문이 원하는 점수보다 높을 경우를 끝에서부터(처음부터) 찾는 시간 복잡도 O(n)에 보다 ✅이분탐색을 통해 O(logN)으로 줄일 수 있다.
(reverse()의 시간복잡도는 O(n))
카카오 공식 설명? 같은걸 봐도 모르겠어서 결국 다른 사람 코드 보고 다시 했다. 이분탐색도 다른사람 풀이 보다가 자꾸 LOWER BOUND 머시기 해서 찾아보고 이분탐색이랑 뭐가 다른지 코테 문제 풀다가 옆길로 빠지고 힘들었당 LOWER BOUND, UPPER BOUND 공부하고 벨로그에 다시 정리하고 싶은데 근로갔다와서 초췌하게 풀어서그런지 내가 멍청한건지 이 문제가 날 매우 힘들게 했기 때무네 난중에 기회되면 정리해야겠다
예~전에도 시도했다가 실패해서 때려치우고 다른거 풀었었는데 사람 쉽게 안변하는 것 같다. 집인데 집가고 싶어서 막 주절주절 적고 있따.
매우 줘옥 같았땅 내가 이 문제 풀려고 몇시간이나 이러고 있었는지 풀이를 대충봐도 몬소린지 몰르겠더라 졸린 상태에서 풀어서 그런가 담에 다시 풀어봐야겠따
22.09.27
다시 풀어도 모르게따 ^9^ 저번엔 졸린 상태라고 합리화했는데 그냥 멍청한거 여따 ^8ㅠ 결국 이전에 풀었던 코드 그대로 암기했다 배껴쓴 사람대따 ^-^사람쉽게 안변한다 ^8^
내코드
처음 효율성 실패 코드
# def solution(info, query):
# answer = [ 0 for i in range(len(query))]
# infosplit = [ i.split(' ') for i in info ]
# infosplit.sort(key = lambda x : int(x[-1]))
# infosplit.reverse()
# infoScore = [int(i.pop()) for i in infosplit]
# querysplit = [ i.replace('and','').replace('-','').split() for i in query ]
# for i in range(len(querysplit)):
# q = querysplit[i].pop()
# for j in range(len(infosplit)):
# if int(q) <= infoScore[j]:
# if len(set(querysplit[i]) - set(infosplit[j])) == 0: answer[i] += 1
# else: break
# return answer진짜 코드
from itertools import combinations
def binary(li,target):
# 항상 범위를 포함해야함 최소 0을 return할 수 있으면 left= -1,
#최대 n-1을 return할 수 있으면 right = n
left = -1
right = len(li)
while left +1 < right:
mid = (left+right) // 2
if li[mid] < target: left = mid
else: right = mid
return right
def solution(info, query):
answer = []
dic = {}
for i in info:
curInfo = i.split(' ')
for j in range(5):
for c in combinations(range(4),j):
temp_info = curInfo[:-1] #깊은 복사
for m in c:
temp_info[m] = '-'
temp_info=''.join(temp_info)
if temp_info in dic: dic[temp_info].append(int(curInfo[-1]))
else: dic[temp_info] = [int(curInfo[-1])]
for v in dic.values(): v.sort()
for q in query:
temp = q.replace('and','').split()
queryKey = ''.join(temp[:-1])
queryScore = int(temp[-1])
if queryKey in dic:
n = binary(dic[queryKey],queryScore)
answer.append(len(dic[queryKey])-n)
else: answer.append(0)
return answer