프로그래머스 순위검색

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

프로그래머스

 

 

처음 풀이

info를 파싱해서 배열에 담는다 : infolist -> 점수를 기준으로 정렬-> query를 순회하면서 이분탐색으로 query에 맞는 info의 갯수를 구한다

-> 시간복잡도에서 틀림

 

수정한 풀이

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

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

우선, 매 문의 조건마다 INFO 배열에서 조건에 해당하는 지원자들을 찾으면서 X점 이상 받은 사람은 몇 명인지 구한다면 정확성 테스트를 통과할 수 있습니다. 그러나 효율성 테스트의 경우에는 위와 같은 방식으로 매번 지원자들을 찾는다면 통과할 수 없습니다. 문제 해결을 위해서, 지원자들을 그룹별로 적절하게 미리 분류해두면 매 문의 조건마다 지원자들을 INFO 배열에서 찾지 않아도 됩니다.

예를 들어, “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 됩니다.

검색 조건이 “java and backend and junior and pizza 100″이라 하면, 위 지원자는 검색 대상에 포함되며, 검색 조건이 “java and – and junior and – 100” 인 경우에도 검색 대상에 포함이 됩니다.

따라서 모든 지원자들을 위와 같은 방식으로 분류한 후 같은 그룹의 지원자끼리 묶어두고, 해당 그룹에서 점수를 기준으로 오름차순 정렬해 둡니다.

이제, 검색 조건이 주어질 경우 INFO 배열에서 지원자들을 찾지 않고, 미리 분류해둔 그룹에서 X점 이상 맞은 지원자 수를 세주기만 하면 됩니다.

이때, X점 이상 맞은 지원자를 찾기 위해 해당 그룹의 최저점, 혹은 최고점부터 순차적으로 검색한다면 여전히 오랜 시간이 걸리게 됩니다. 이때, 숫자가 오름차순으로 정렬된 배열에서 X라는 숫자를 찾는 효율적인 방법으로 binary search를 사용할 수 있습니다. 이때, 배열에 X가 없을 수도 있으므로, 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 하며, 이는 lower bound를 이용하면 됩니다.

 

풀이

1. info를 파싱해서 배열에 담는다 : infolist 

for i in info:
        parsed = i.split(" ")
        score = int(parsed[-1])
        parsed[-1] = score
        infolist.append(parsed)

 

2. (언어, 직군, 경력, 소울푸드)를 key로 하고 value는 빈배열로 하는 dictionary를 만든다

def makeDict():
    langs = ["cpp", "java", "python", "-"]
    jobs = ["backend", "frontend", "-"]
    exps = ["junior", "senior", "-"]
    sfoods = ["chicken", "pizza", "-"]
    
    for lang in langs:
        for job in jobs:
            for exp in exps:
                for food in sfoods:
                    key = (lang, job, exp, food)
                    val = []
                    dict[key] = val

 

3. info를 dictionary에 담는다.

def makeGroup():
    global n
    for info in infolist:
        clang, cjob, cexp, cfood = info[:4]
        key = ['-', '-', '-', '-']
        langs = [clang, '-']
        jobs = [cjob, '-']
        exps = [cexp, '-']
        foods = [cfood, '-']
        for a in range(2):
            for b in range(2):
                for c in range(2):
                    for d in range(2):
                        key = (langs[a], jobs[b], exps[c], foods[d])
                        dict[key].append(info)

 

4. dictionary에서 key - query, value - 해당 쿼리에 해당하는 info 배열을 조회한 후 이분탐색

def qCnt(parsed):
    global n
    result = 0 
    score = int(parsed[-1])
    lang, job, exp, food = parsed[:4]
    query = (lang, job, exp, food)
    result = bsearch(score, query)
    return result

 

 

정답 코드

infolist = []
querylist = []
dict = {}
n = 0
def solution(info, query):
    global n
    answer = [] 
    n = len(info)
    for i in info:
        parsed = i.split(" ")
        score = int(parsed[-1])
        parsed[-1] = score
        infolist.append(parsed)
    makeDict()
    makeGroup()
    for key, val in dict.items():
        val.sort(key = lambda x: x[-1])
        
    for q in query:
        parsed = [word for word in q.split(" ") if word != "and"]
        cnt = qCnt(parsed)
        answer.append(cnt)
        
    return answer

def makeDict():
    langs = ["cpp", "java", "python", "-"]
    jobs = ["backend", "frontend", "-"]
    exps = ["junior", "senior", "-"]
    sfoods = ["chicken", "pizza", "-"]
    
    for lang in langs:
        for job in jobs:
            for exp in exps:
                for food in sfoods:
                    key = (lang, job, exp, food)
                    val = []
                    dict[key] = val
def makeGroup():
    global n
    for info in infolist:
        clang, cjob, cexp, cfood = info[:4]
        key = ['-', '-', '-', '-']
        langs = [clang, '-']
        jobs = [cjob, '-']
        exps = [cexp, '-']
        foods = [cfood, '-']
        for a in range(2):
            for b in range(2):
                for c in range(2):
                    for d in range(2):
                        key = (langs[a], jobs[b], exps[c], foods[d])
                        dict[key].append(info)


def bsearch(target, query):
    arr = dict[query]
    arrlen = len(arr)
    start = 0
    end = arrlen - 1
    while start <= end: 
        mid = (start + end) // 2
        score = arr[mid][-1]
        if  score == target:
            temp = arrlen - mid
            # 이분탐색 시 mid 아래 index에 동일한 score인 것 처리
            for m in range(mid-1, -1, -1):
                tscore = arr[m][-1]
                if tscore < target:
                    break
                else:
                    temp+= 1
            return temp
        elif score > target:
            end = mid - 1
        else:
            start = mid + 1
    result = arrlen - start        
    return result

def qCnt(parsed):
    global n
    result = 0 
    score = int(parsed[-1])
    lang, job, exp, food = parsed[:4]
    query = (lang, job, exp, food)
    result = bsearch(score, query)
    return result