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

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

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

 

 

<문제 설명>

위와 같은 데이터가 주워진다.

info는 지원자들의 정보와 코딩테스트 점수이며, query는 조건을 의미한다.

최종 답은 각 query에 만족하는 지원자가 몇명인지를 담고 있는 배열이다.

query 속 '-'는 해당 조건을 고려하지 않는다는 것을 의미한다.

 

 

 

<시행 착오>

<문제 이해>

처음에 일단 문장으로 되어있는 데이터를 split()함수를 사용해

하나하나 비교하면 되겠다고 생각했다.

 

<문제 풀이>

def solution(info, query):
    answer = []
    
    for qlist in query:
        q = (''.join(qlist.split("and"))).split()
        count = 0
        for ilist in info:
            i = ilist.split()
            if (q[0] == i[0] or q[0] == '-') and (q[1] == i[1] or q[1] == '-') and (q[2] == i[2] or q[2] == '-') and (q[3] == i[3] or q[3] == '-') and (int(q[4]) <= int(i[4])):
                count += 1
                
        answer.append(count)
        
    return answer

 

먼저 query의 데이터를 and를 기준으로 자르고 공백을 기준으로 한 번 더 잘랐다.

그리고 info의 데이터와 하나하나 비교했다.

이렇게 풀었더니 정확성 테스트는 통과했지만, 효율성 테스트는 통과하지 못했다.

 

 

 

 

<문제 풀이>

결국 해결하지 못하고 해설을 보았다 ㅎㅎ

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

 

먼저 info의 지원자들의 데이터를 이용해 쿼리에서 나올 수 있는 모든 경우의 수를 미리 준비하고,

그에 맞는 값으로 배열형태의 코딩테스트 점수를 넣는 것이다.

이를 이용해 query에서 필요한 데이터를 찾아서 쓸 수 있도록 하는 것이 효율성을 높이는 방법이라고 했다.

 

즉, 코딩테스트를 제외한 4개의 조합을 key로, 코딩테스트 점수를 value로하는 딕셔너리를 

만들고 그에 해당하는 값으로 코딩테스트 점수를 넣어 놓고, query의 조건을 만족하는 값을 찾는 것이다.

 

그리고 기준 코딩테스트 점수 이상을 받을 사람의 수를 찾아야 한다.

선형검색도 시간이 오래걸리기 때문에 이진탐색을 이용해서 구하는 것이 더 효율적이다.

이진탐색을 하기 위해선 데이터 정렬이 필수적으로 이루어져야 한다.

 

import itertools

def solution(info, query):
    answer = []
    dic = {}
    query = [''.join(x.split('and')).replace('-','').split() for x in query]	# and와 - 제외한 배열

    for i in info:			# 각 조합의 딕셔너리 만들기
        li = i.split()
        for j in range(len(li)):
            li2 = list(itertools.combinations(li[:-1],j))
            for k in li2:
                temp = ''.join(k)
                if temp not in dic: dic[temp] = [int(li[-1])] 
                else: dic[temp].append(int(li[-1]))   

    for d in dic.values():		# 조합의 코테 점수 배열 정렬
        d.sort()

    for q in query:			# 쿼리에 속한 값 찾기 & 코테 점수 만족하는 사람 수 찾기
        combi = ''.join(q[:len(q)-1])
        if combi not in dic : answer.append(0); continue
        else:
            length = len(dic[combi])
            slist = dic[combi]
            
            # 이진탐색 (lower bound : 타겟보다 크거나 같은 수 찾기)
            start = 0
            end = length
            while start < end:
                mid = (start+end)//2
                if int(q[-1]) <= slist[mid]: end = mid
                elif int(q[-1]) > slist[mid]: start = mid + 1
            answer.append(length-end)

    return answer

 

처음에 풀 때는 중간에 데이터 정렬을 해주지 않고, 쿼리에서 하나씩 찾을 때 정렬을 해주었다.

난 이렇게 해도 된다고 생각했는데 효율성 테스트가 계속 시간 초과가 났다... 왜그럴까.

아직도 이해 못함;;

 

 

 

 

암튼 쉬운 문제인줄 알고 신나게 풀다가 코깨졌다,,, 후,,,

암튼 간만에 itertools 복습할 수 있어 좋았ㄷ,,,