[파이썬] 프로그래머스 : 순위 검색 (Lv.2)

[파이썬] 프로그래머스 : 순위 검색 (Lv.2)

 

프로그래머스

 

---

풀이

0. 방향성 생각

데이터, 쿼리의 수가 5만,10만으로 서로 체크할 경우 50억. 당연히 시간초과.

후보를 줄여나가서 for문을 돌려도 데이터 5만에서 언어 1/3, 나머지 1/2씩 3개 해도 1/24 하면 약 2000개

이상적인 케이스에 대해서도 쿼리랑 곱해주면 약 2억이라 간당간당하다.

효율성 테스트 검사하는 문제라서 사실상 틀렸다고 생각하고 다른 풀이 찾는게 맞음

 

처음 풀이

1. 각 영역 set에 지원자 정보 저장, 마지막에 지원자 점수 매칭 속도를 높이기위해 딕셔너리에 점수 매칭

2. 쿼리 전처리 ['java and backend and junior and pizza score], score  -> ['java','backend','junior','pizza'], score 

3. 조건 순서대로 set 불러와서 교집합 연산 + 마지막에 for문으로 카운트

 

이후 풀이

처음 풀이

1. 각 영역 set에 지원자 정보 저장, 모든 조건별로 딕셔너리에 점수 저장.

2. 쿼리 전처리 ['java and backend and junior and pizza score], score  -> ['java','backend','junior','pizza'], score 

3. 이분탐색

1. 지원자 정보 업데이트

from itertools import combinations as C

def solution(infos,querys):
    
    table = {}
    for idx,info in enumerate(infos):
        temp = info.split() # idx번 째 지원자 [언어,직무,경력,소울푸트]
        score = int(temp.pop()) # idx번 째 지원자 점수
        for i in range(5):
            comb = list(C(temp,i)) # 조건 0개 ~ 4개
            for s in comb: # 전부 테이블에 추가
                info_string = ''.join(s)
                if info_string not in table : table[info_string] = [score]
                else : table[info_string].append(score)               
    for key in table.keys(): # 정렬
        table[key].sort()

언어,직군,경력,소울푸드 중 0~4개를 골라서 하나의 key로 통합시킨다.

딕셔너리 value에는 지원자 점수 저장

전부 업데이트 후 이분탐색을 위한 정렬.

2. 조건식 전처리

    conditions = [] # 조건식 전처리
    for query in querys:
        temp = query.split(' and ') # 나눠주고
        food,score = temp[-1].split()
        temp[-1] = food
        temp = [i for i in temp if i != '-']
        query_string = ''.join(temp)
        conditions.append([query_string,int(score)])

쿼리 전처리 ['java and backend and junior and pizza score], score  -> ['java','backend','junior','pizza'], score 

' and '로 나눈 후 소울푸드와 점수만 따로 한 번 더 처리를 해준다.

 

2. 이분탐색 + 출력

    def binary_search(search_list,target): # 이분탐색    

        start,end = 0,len(search_list)-1
        while start <= end:
            mid = (start+end) // 2
            if search_list[mid] < target : start = mid + 1
            else : end = mid - 1
        return len(search_list)-start # 목표값 이상 개수

    answer = []
    for query_string,goal in conditions: # 조건, 목표값
        if query_string in table:
            answer.append(binary_search(table[query_string],goal))
        else:
            answer.append(0)
    return answer

이분탐색 함수 만들고

조건식 변경한 conditions의 key와 타겟점수 goal을 이분탐색 시키고 조건 만족하는 개수 리턴

---

전체코드

from itertools import combinations as C

def solution(infos,querys):
    
    table = {}
    for idx,info in enumerate(infos):
        temp = info.split() # idx번 째 지원자 [언어,직무,경력,소울푸트]
        score = int(temp.pop()) # idx번 째 지원자 점수
        for i in range(5):
            comb = list(C(temp,i)) # 조건 0개 ~ 4개
            for s in comb: # 전부 테이블에 추가
                info_string = ''.join(s)
                if info_string not in table : table[info_string] = [score]
                else : table[info_string].append(score)               
    for key in table.keys(): # 정렬
        table[key].sort()

    conditions = [] # 조건식 전처리
    for query in querys:
        temp = query.split(' and ') # 나눠주고
        food,score = temp[-1].split()
        temp[-1] = food
        temp = [i for i in temp if i != '-']
        query_string = ''.join(temp)
        conditions.append([query_string,int(score)])
    
    def binary_search(search_list,target): # 이분탐색    

        start,end = 0,len(search_list)-1
        while start <= end:
            mid = (start+end) // 2
            if search_list[mid] < target : start = mid + 1
            else : end = mid - 1
        return len(search_list)-start # 목표값 이상 개수

    answer = []
    for query_string,goal in conditions: # 조건, 목표값
        if query_string in table:
            answer.append(binary_search(table[query_string],goal))
        else:
            answer.append(0)
    return answer

 

코멘트

처음에 모든 경우의수 고려해서 딕셔너리에 저장하는거 생각은 했었는데

한 사람 데이터 추가할 때 4C0 + 4C1 + 4C2 + 4C3 + 4C4 = 2^4, 16개 리스트 싹다 업데이트해서

시간적으로도 손해고, 메모리도 터져나갈거같아서 그냥 풀었는데 당연히 시간초과...

데이터랑 쿼리 수만 봐도 2중 for문은 아니라서 잘 생각했어야 됐는데 이분탐색을 잘 안써서 생각못함.

 

그냥 푸는거는 쉬운데 효율성 맞추는 풀이 생각하는게 어려운듯.

테케도 효율성이 4개밖에 없는데 비중은 60프로라서 실전이었으면 망했을듯

 

---

처음 코드

def solution(info, query):
    
    infos_set = [] # [[{직군,언어,경력,음식},점수]]
    for data in info:
        temp = data.split()
        temp[-1] = int(temp[-1])
        infos_set.append([set(temp[:4]),temp[-1]])
        
    conditions = [] # 전처리
    for data in query:
        temp = data.split(' and ') # 나눠주고
        food,score = temp[-1].split()
        temp[-1] = food
        temp.append(int(score))
        temp2 = set(temp[:-1])
        temp2.discard('-')
        conditions.append([temp2,temp[-1]])
    
    for i in conditions:
        print(i)
        
    answer = []
    for cond_set,cond_score in conditions: # 쿼리 조건
        count = 0
        for info_set,info_score in infos_set: # 사람들 정보 [[{직군,언어,경력,음식},점수]]
            if info_set&cond_set == cond_set and info_score >= cond_score:
                count += 1
        answer.append(count)
    return answer