[Python][프로그래머스] level 2 - 순위 검색 (딕셔너리, 이진탐색)

문제

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

 

풀이과정

처음에는 제한사항을 제대로 보지않고 
하나의 query 가 들어올때마다 info 배열을 전부 확인하면서 조건에 만족하는 지원자의 수를 세는 완전탐색 방식으로 풀었습니다.

하지만 이런 제한사항이 있는데 될리가있나...ㅎ 
정확도는 전부 맞았지만 효율성은 가차없이 0점이 나왔습니다 😂

완전탐색으로 푼 코드는 아래와 같습니다.

Code 1 (정확성 18/18 효율성 0/4)

def isCorrect(query, info):
    for idx in range(4):
        if not (query[idx] == '-' or query[idx] == info[idx]):
            return False
    if int(query[4]) <= int(info[4]):
        return True
    return False

def solution(info, query):
    infoArr = []
    queryArr = []
    for x in info:
        infoArr.append(list(x.split(" ")))
    for x in query:
        queryArr.append(list(y for y in x.replace("and", "").split(" ") if len(y) > 0))
    
    answer = []
    for query in queryArr:
        temp = 0
        for info in infoArr:
            if isCorrect(query, info):
                temp += 1
        answer.append(temp)
    return answer

 

시간초과 해결한 풀이과정

시간초과를 해결하기 위해 방법은 카카오 문제해설을 참고했습니다.

1) info 를 통해 통과가능한 query 들을 미리 계산해 전부 딕셔너리에 저장한다.

info 가 통과가능한 query 들과 그 점수를 key-value 로 딕셔너리에 저장한다면, query 가 주어졌을 때 info 를 전부 확인하지 않고 하나의 key 에만 접근하면 됩니다.

그러면 info가 통과가능한 query들을 계산해서 딕셔너리에 저장하는 과정을 살펴볼까요?
info 가 "java backend junior pizza 150" 일때 통과할 수 있는 query 들은 아래와 같이 계산할 수 있습니다.

이렇게 계산된 query 들을 딕셔너리에 저장해야하는데 딕셔너리의 key 는 유일해야하고 배열로 저장할 수 없습니다.
그렇기때문에 이를 유일한 문자열로 변경하는 과정이 필요합니다. 

def make_case(x, infoDict):
    tempArr = x.split(" ")
    score = int(tempArr[-1])
    for idx in range(5):
        for c in combinations(tempArr[:-1], idx):
            key = "".join(c)
            if key in infoDict:
                infoDict[key].append(score)
            else:
                infoDict[key] = [score]

 

예시의 값을 info 로 입력받아 위의 코드를 실행시키면

입력값 〉

["java backend junior pizza 150", "python frontend senior chicken 210", "python frontend senior chicken 150", "cpp backend senior pizza 260", "java backend junior chicken 80", "python backend senior chicken 50"]

이와 같이 딕셔너리가 채워지는 것을 확인할 수 있습니다.

 

2) 퀴리의 조건을 info 의 key와 같은 형태으로 만들고 queryScore 보다 큰 값들의 개수를 저장한다.

이제 쿼리들을 딕셔너리의 key 와 같은 형태로 만들고 queryScore 를 계산한 다음

tempArr = list(y for y in x.replace("and", " ").replace("-", "").split(" ") if len(y) > 0)
queryScore = int(tempArr[-1])

해당 key 가 딕셔너리에 값이 있는지, 있다면 query 에 있는 점수보다 크거나 같은 점수는 몇개가 있는지 계산하기만 하면 됩니다. 하지만 만약 하나의 쿼리에 속한 점수들의 배열이 너무 길어서 검색하는 시간이 길어져 시간초과 날수도 있습니다.

이를 해결하기위해 이분탐색을 사용할 예정이므로 미리 value 들을 정렬해둡니다.

for key in infoDict.keys():
    infoDict[key].sort()

 

그리고 lower_bound 를 계산해주는 bisect_left 를 통해 query 내의 점수보다 점수가 높은 개수를 계산하여 출력하면 됩니다.

answer = []
for x in query:
	tempArr = list(y for y in x.replace("and", " ").replace("-", "").split(" ") if len(y) > 0)
	queryScore = int(tempArr[-1])
	if len(tempArr) == 1:
		answer.append(find_answer("", queryScore, infoDict))
	else:
		answer.append(find_answer("".join(tempArr[:-1]), queryScore, infoDict))

 

이 과정을 거치면 드디어 효율성을 통과할 수 있습니다. 😝😝😝😝

 

전체 코드는 아래와 같습니다.

Code 2 (정확성 18/18 효율성 4/4)

from itertools import combinations
from bisect import bisect_left

# java backend junior pizza 를 "backendjuniorpizza", "junior pizza" ... ""
# 위와 같이 가능한 모든 경우의 수 dict 에 넣기
def make_case(x, infoDict):
    tempArr = x.split(" ")
    score = int(tempArr[-1])
    for idx in range(5):
        for c in combinations(tempArr[:-1], idx):
            key = "".join(c)
            if key in infoDict:
                infoDict[key].append(score)
            else:
                infoDict[key] = [score]

# 이진탐색으로 queryScore 보다 큰 점수들의 개수 반환
def find_answer(key, queryScore, infoDict):
    if key in infoDict:
        return len(infoDict[key]) - bisect_left(infoDict[key], queryScore)
    return 0

def solution(info, query):
    infoDict = dict()
    
    for x in info:
        make_case(x, infoDict)
    
    for key in infoDict.keys():
        infoDict[key].sort()
        
    answer = []
    for x in query:
        tempArr = list(y for y in x.replace("and", " ").replace("-", "").split(" ") if len(y) > 0)
        queryScore = int(tempArr[-1])
        if len(tempArr) == 1:
            answer.append(find_answer("", queryScore, infoDict))
        else:
            answer.append(find_answer("".join(tempArr[:-1]), queryScore, infoDict))
            
    return answer

 

Combination 과 Bisect 를 직접 구현하기

만약 코딩테스트에서 import 가 금지되어있을 경우를 대비하여 combination 과 bisect 를 직접 구현하는 방식도 알아보자!
python 으로 조합을 구현한 코드는 아래와 같고 자세한 설명은 순열과 조합 직접 구현하기 / itertools 사용하기에서 확인할 수 있다.

def combinations(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            for next in combinations(array[i+1:], r-1):
                yield [array[i]] + next

python 으로 bisect_left를 직접 구현한 코드는 아래과 같다.

def bisect_left(arr, value, begin, end):
    if begin >= end:
        return begin
    mid = begin + (end - begin) // 2
    if arr[mid] < value:
        return bisect_left(arr, value, mid + 1, end)
    else:
        return bisect_left(arr, value, begin, mid)

 

참고

- https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/
- https://zygygy.github.io/Binary-Search-1