순위 검색

개발새발log·2022년 4월 24일

level2 코딩테스트

Programmers

목록 보기

19/35

문제: 순위 검색

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

레벨2라는 걸 받아들이기 힘든 문제...💩

푸는 과정에서 배울 게 많은 문제여서 기록하고자 한다.

정확성, 효율성 테스트 점수가 있는 문제다. 이렇게 대놓고 명시하는 경우 제한사항을 눈여겨 봅시다!!

초기 접근 방식: 효율성 검사 실패

def solution(info, query):
    info_arr = [a.split() for a in info]
    query_arr = [b.split() for b in query]

    res = []
    for query in query_arr:
        cur_res = 0
        for info in info_arr:
            lang, part, exp, food, score = info[0], info[1], info[2], info[3], info[4]
            if query[0] == '-': lang = '-'
            if query[2] == '-': part = '-'
            if query[4] == '-': exp = '-'
            if query[6] == '-': food = '-'
            if query[0] == lang and query[2] == part and query[4] == exp and query[6] == food and int(score) >= int(query[7]):
                cur_res += 1
        res.append(cur_res)
    return res

주어진 조건을 주의해야 한다 ⬇️
info 배열의 크기는 1 이상 50,000 이하입니다.
query 배열의 크기는 1 이상 100,000 이하입니다.

이렇게 query 별, info 별 이중 for문을 돌 경우 O(N*M)으로, 최악의 경우 5억 번의 연산을 하게 된다.

수정 후

위 방식대로는 영 아닌 거 같길래 카카오tech 문제해설을 참고했다.

from itertools import product
from collections import defaultdict
from bisect import bisect_left

def make_dictionary(info):
    dictionary = defaultdict(list)
    for x in info:
        for p in product([x[0], "-"], [x[1], "-"], [x[2], "-"], [x[3], "-"]):
            dictionary[p].append(int(x[4]))
    #선소팅
    for _, val in dictionary.items():
        val.sort()
    return dictionary

def solution(info, query):
    info = [a.split() for a in info]
    #1
    dictionary = make_dictionary(info)
    #2
    result = []
    for q in query:
        l, _, p, _, c, _, f, point = q.split()
        idx = bisect_left(dictionary[(l, p, c, f)], int(point))
        result.append(len(dictionary[(l, p, c, f)]) - idx)
        
    return result

크게 두 파트로 나눌 수 있다:

주어진 info 배열을 모든 경우의 수를 고려한 dictionary로 만들기
해당 dictionary의 list를 빠르게 탐색하기 위해 이진탐색을 이용할 것

코드 해설

1.

✅ 주어진 info 배열을 모든 경우의 수를 고려한 dictionary로 만들기

def make_dictionary(info):
    dictionary = defaultdict(list)
    for x in info:
        for p in product([x[0], "-"], [x[1], "-"], [x[2], "-"], [x[3], "-"]):
            dictionary[p].append(int(x[4]))
    #선소팅
    for _, val in dictionary.items():
        val.sort()
    return dictionary

product는 데카르트 곱을 만드는데 유용한 내장함수다.
⬇️ 아래 블로그 참고
https://stackstackstack.tistory.com/entry/python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%ED%95%A8%EC%88%98-product-permutations-combinations

product로 info에서 나올 수 있는 모든 경우의 수를 조합했다
(java, backend, junior, pizza)
(java, backend, junior, -)
(java, backend, -, pizza)
(java, -, junior, pizza)
(java, -, -, pizza)
등등등

info 하나당 2*2*2*2로, 총 16가지 조합이 나올 수 있다.
dictionary를 만들어, 해당 조합의 value에 점수를 append 했다
👉 dictionary = defaultdict('list')

결국, 이런 식으로 저장되는거다
dictionary[(java, backend, junior, pizza)] = 150
dictionary[(java, backend, junior, -)] = 150
dictionary[(java, backend, -, pizza)] = 150
dictionary[(java, -, junior, pizza)] = 150
dictionary[(java, -, -, pizza)] = 150

처음에 여러 값을 저장하는 형태의(ex. list, tuple) key가 가능한가 잠깐 고민했는데 key는 불변의 값이면 괜찮다고 한다. (tuple을 key로 가질 순 있다는 것이다)

이렇게 dictionary를 만들고나서 그 다음 중요한 건 선 sorting하는 것이다. dictionary에 포함된 list 역시 길어질 수 있기에, 빠른 탐색을 위해 이진 탐색을 하고자 하는데, 이를 위해서는 정렬이 선행되어야 하기 때문이다.

2.

✅ 해당 dictionary의 list를 빠르게 탐색하기 위해 이진탐색을 이용할 것
(사실 탐색은 그냥 빠른 탐색법을 택하면 될 거 같다)

result = []
    for q in query:
        l, _, p, _, c, _, f, point = q.split()
        idx = bisect_left(dictionary[(l, p, c, f)], int(point))
        result.append(len(dictionary[(l, p, c, f)]) - idx)