순위 검색 [프로그래머스]

효율성 부들부들

문제 풀이 정리

 

문제 설명 보고 개쉽네ㅋ 하고 입장했다가 대가리 깨진 문제다.

 

일단 문제자체는 어렵지 않다. 조건에 맞는 score들만 가져와서 개수를 센다. 끝 :)

 

그렇게 안일하게 보고 코드를 짤 경우 for loop *4 의 지옥을 보고 어...? 이거 괜찮은가? 하면서 돌리게 된다.

물론 그럼 시간 초과 난다. (테스트는 통과하지만 효율성에서 막힌다.)

 

그럼 두번째 방법으로 생각 한 것이 json처럼 depth 구분이 있게끔 만들어서 조건에 맞는 애들만 좀 쉽게 관리하자! → dictionary 형태로 key:value 로 만들어 관리

but, 마지막 depth 의 score_list에서 특정 값이상의 숫자 개수를 반환하는데 있어서 효율성 탈락

 

자, 그럼 score_list에서 빠르게 꺼낼 방법을 찾아야 한다.

lower bound 알고리즘을 사용해야 한다. 이진 탐색의 한 방법으로 배열의 중간 값을 보고 처음 시작과 끝 index를 옮기며 비교하는 알고리즘이다. (start_index == end_index 일때 해당 알고리즘 종료)

 

lower bound 를 사용했음에도 효율성 통과 x

→ 해당 풀이할때 문제점은 query 반복때 마다 sort해서 문제 였다.

(lower bound 사용시 정렬이 되어 있어야 하는 문제점 발생)

 

그래서 score_list에 삽입이 전부 완료된 뒤, 한번! sort 해주고 query 를 비교해줬다.

 

def prev_solution(info, query): # 안일한 첫번째 시도
    
    info = [x.split(" ") for x in info]
    
    for qi in query:
        qi = qi.replace(" and "," ").split(" ")
        
        temp_list = list(info)
        for index, q in enumerate(qi): 
            if q == "-":
                continue
            result_list = []
            for temp_info in temp_list:
                if index != 4:
                    if temp_info[index] == q:
                        result_list.append(temp_info)
                else:
                    if int(temp_info[index]) >= int(q):
                        result_list.append(temp_info)
            temp_list= list(result_list)
        
        answer.append(len(temp_list))

def prev_solution_2(info, query): #lower bound 없이 depth 구분으로 풀려했던 시도
    answer = []
    
    lang = ['cpp','java','python']
    position = ['frontend','backend']
    career = ['junior','senior']
    food = ['chicken','pizza']
    
    info_dict = {}
    for l in lang:
        p_dict = {}
        for p in position:
            c_dict = {}
            for c in career:
                f_dict = {}
                for f in food:
                    f_dict[f] = []
                c_dict[c] = f_dict
            p_dict[p] = c_dict
        info_dict[l] = p_dict
    
    info = [x.split(" ") for x in info]
    for i in info:
        lang_ = i[0]
        position_ = i[1]
        career_ = i[2]
        food_ = i[3]
        score = int(i[4])
        info_dict[lang_][position_][career_][food_].append(score)
    
    query_list = [q.replace(" and "," ").split(" ") for q in query]
    for query in query_list:
        lang_ = []
        if query[0] == "-":
            lang_ = lang
        else:
            lang_ = [query[0]]
            
        position_ = []
        if query[1] == "-":
            position_ = position
        else:
            position_ = [query[1]]
        
        career_ = []
        if query[2] == "-":
            career_ = career
        else:
            career_ = [query[2]]
        food_ = []
        if query[3] == "-":
            food_ = food
        else:
            food_ = [query[3]]
        score_ = int(query[4])
        
        count = 0
        score_list = []
        for l in lang_:
            for p in position_:
                for c in career_:
                    for f in food_:
                        score_list.extend(info_dict[l][p][c][f])
        score_list = sorted(score_list)
        
        start = 0
        end = len(score_list)
        mid = 0
        while True:
            mid = (start+end) // 2
            if score_list[mid] >= score_:
                if end == mid:
                    break
                end = mid
            else:
                break
        
        count = 0
        for index,score in enumerate(score_list[mid:], start=mid):
            if score >= score_:
                count = len(score_list) - index
                break
        answer.append(count)
        
def solution(info, query): #depth 구분없이 발생가능한 문자열로key:value -> sort ->lowerbound
    answer = []
    
    lang = ['cpp','java','python','-']
    position = ['frontend','backend','-']
    career = ['junior','senior','-']
    food = ['chicken','pizza','-']
    
    temp_dict = dict()
    for l in lang:
        for p in position:
            for c in career:
                for f in food:
                    temp_dict[l+p+c+f] = []
    info = [x.split(" ") for x in info]
    for i in info:
        lang_ = [i[0],'-']
        position_ = [i[1],'-']
        career_ = [i[2],'-']
        food_ = [i[3],'-']
        score = int(i[4])
        
        for l in lang_:
            for p in position_:
                for c in career_:
                    for f in food_:
                        temp_dict[l+p+c+f].append(score)
    
    for l in lang:
        for p in position:
            for c in career:
                for f in food:
                    temp_dict[l+p+c+f] = list(sorted(temp_dict[l+p+c+f]))
    
    query_list = [q.replace(" and "," ").split(" ") for q in query]
    for query in query_list:
        q = query[0]+query[1]+query[2]+query[3]
        score = int(query[4])
        score_list = temp_dict[q]#list(sorted(temp_dict[q]))
        
        start = 0
        end = len(score_list)
        while True:
            if start == end:
                break
                
            mid = (end + start) // 2
            if score_list[mid] < score:
                start = (mid+1)
            elif score_list[mid] >= score:
                end = mid
        #print(len(score_list)-start)        
        count = len(score_list)-start #len(score_list[start:])
        
        answer.append(count)
    return answer

 

문제는 여기

https://programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색