(Week3)[구현] 순위검색

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 40분 + a

1. 문제 설명

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

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

코딩테스트에 참여한 사람들의 정보를 검색하기 위한 알고리즘 작성

2. 접근 방식

2-1. 초기 접근방식 (효율성 통과 X)

• 문자열은 split으로 저장하면 된다.
• 순서대로 반환해야 하기 때문에 리스트로 접근하자.
• `-`인 경우는 사실상 True이고, 하나라도 다르다면 나가기 False

2-1. 스터디에서 알게 된 접근 방식

• Combination을 활용해서 나올 수 있는 검색 경우의 수를 구한다(점수 제외). (언어:3, 직군:2, 경력:2, 푸드:2, 점수: 100000)
• 이렇게 나온 다양한 경우들을 key로 하는 딕셔너리를 만들어, 해당 key에 해당하는 점수들을 넣어준다.
  • 'java_backend_-_-': [150, 80]의 꼴
•  해당 키 값들의 점수 리스트를 낮은 순서대로 정렬한다. (이진탐색을 위함)
  • 'java_backend_-_-': [80, 150]으로 정렬
•  검색이 들어오면, 키와 같은 꼴로 만들어 해당 키의 값에서 해당하는 점수들을 찾아 개수를 리턴해준다.   

3. 코드

코드 (효율성 통과X)

def solution(info, query):
    info_ls = [person.split() for person in info]
    query_ls = [question.split(' and ') for question in query]
    answer = []

    for question in query_ls:
        language, job, js, food_score = question
        food, score = food_score.split()
        sample = [language, job, js, food, score]
        count = 0
        for per in info_ls:
            per_count = 0
            for i, j in zip(per[:4], sample[:4]):
                if i == j or "-" == j:
                    per_count += 1
            if int(per[4]) >= int(sample[4]):
                per_count += 1
            if per_count == 5:
                count+=1
        answer.append(count)
    return answer

코드 (해답)

from collections import defaultdict
from itertools import combinations
from bisect import bisect_left, bisect_right


def solution(info, query):
    answer = []
    db = defaultdict(list) # defaultdict 키 값이 없어도 dict생성
    for i in info:
        temp = i.split()
        conditions = temp[:-1]
        score = temp[-1]

        # '-'가 올 수 있는 모든 경우의 수 구하기 -> 0번 오는 경우 ~ 4번 오는 경우
        for r in range(5):
            combis = list(combinations(range(4), r)) # 인덱스
            # 위에서 구한 경우의 수에 '-'를 넣어 조합 만들기
            for combi in combis:
                test_case = conditions.copy()
                for c in combi:
                    test_case[c] = '-'
                db['_'.join(test_case)].append(int(score))
                #'java_backend_-_-': [150, 80]의 꼴
    # 점수 정렬
    for item in db:
        db[item].sort() #'java_backend_-_-': [80, 150]으로 정렬
    for q in query:
        temp = q.split()
        conditions = '_'.join(temp[0::2])  # db형식에 맞게 원하는 조건 맞추기 (and 뛰고 key생성)
        target = int(temp[-1])
        db_users = db[conditions]        
        if db_users:
            left_index = bisect_left(db_users, target)
            answer.append(len(db_users) - (left_index))
        else:
            answer.append(0)
    return answer

4. 코멘트

• 혼자 풀 때는 시간이 부족해서 오래 생각하지 못하고, 효율성 문제에서도 걸렸었는데, 스터디를 통해서 접근 방법 자체가 너무 단순했다는 것을 알게 됐다.
• 해당 문제에서는 combinations와 이진탐색이 핵심이었다. 조합을 사용하면 시간이 많이 소요될 것 같았는데, 해당 문제의 경우 검색이 100,000이었고, info가 50,000이었다. 따라서 초기 코드대로라면 100,000 x 50,000의 시간이 소요됐을 것이다. 하지만 해답 코드의 경우 info 구축에 시간이 소요될 지라도 검색 시에는 매우 빠르게(dict) 접근할 수 있었기 때무넹 효율성을 통과할 수 있었다. 인덱스를 통한 접근이라는 점에서 엘라스틱 서치와 유사하지 않았나 생각이 든다. 
• '-'의 경우가 들어가기 때문에, 이를 활용해, 조합을 만든 것이 참신했다. 
• 또한 space를 기준으로 split을 해서 리스트 인덱싱 시 jump 변수를 줘서 필요한 정보만 뽑는 점이 좋았다.
• 팀원이 알려줬던 코드에서 bisect라이브러리를 활용했을 때, 기존 코드 대비 효율성 테스트에서 400ms 이상 차이가 났다. 알고리즘에 대한 이해가 필요한 게 아니라면 bisect 라이브러리를 활용하는 게 좋아보인다.  

# 이진탐색 알고리즘1
start, end = 0, len(db_users)
# 이진 탐색
while start != end:
    mid = (start + end) // 2
    if db_users[mid] >= int(target):
        end = mid
    else:
        start = mid + 1
answer.append(len(db_users) - start)


# 이진탐색 알고리즘2 (bisect 라이브러리)
from bisect import bisect_left
left_index = bisect_left(db_users, target)
answer.append(len(db_users) - (left_index))