LV2 [KAKAO] 순위 검색

---

문제

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

프로그래머스

 

풀이

 

문제를 보고서 Dictionary를 사용해야할 거 같았다.

1. 우선 주어진 프로그래밍 언어, 직군 등을 조합하고 모든 부분집합을 Key로 만들어주고 초기화해준다.

 

2. 이후에 info 리스트를 순회하면서 모든 부분집합을 만들고, 해당하는 Key에 점수를 넣어준다. 

 

3. 마지막에는 query 리스트를 순회하면서 해당 조건에 맞는 Key를 찾고, value (점수들이 들어가있는 list) 를 뒤지면서 해당점수 이상 점수들이 몇 개 있는지 알아내면 된다.

 

여기까지 생각하는건 어렵지 않았고, 정확성도 다 맞출 수 있었다. 그러나 문제는 시간이었다.

 

내가 개선했던 점은

 

1. 처음에는 선형탐색으로 점수들을 체크했는데, sort후에 bisect 라이브러를 이용하여 이분탐색으로 순위를 알아냈다.

 

2. 쿼리문이 최대 100,000개 라는걸 고려했을 때 분명 중복되는 쿼리문이 있을 수 있겠구나 라고 생각했다. 이전에 구조는 점수 list를 항상 sort했는데 이미 sort 되어있는것은 안해도 되겠구나 라고 생각했다. 따라서 sort 되어있는 key들을 저장하고 불필요한 sort를 하지 않도록 수정하였다.

 

1번을 하고나서는 여전히 시간초과였는데, 2번까지 하니 통과할 수 있었다!

 

 

코드

import bisect

def dfs(temp, idx, s, d):

    # 문장이 완성되었다면
    if idx >= 4:
        d[s].append(int(temp[4]))
        return

    dfs(temp, idx+1, s+temp[idx], d)
    dfs(temp, idx+1, s, d)

def solution(infos, querys):

    lang = ['java', 'python', 'cpp']
    job = ['backend', 'frontend']
    career = ['junior', 'senior']
    food = ['chicken', 'pizza']
    answer = []

    d = {}

    for i in range(4):
        for j in range(3):
            for k in range(3):
                for l in range(3):
                    s = ''
                    if i != 3: s += lang[i]
                    if j != 2: s += job[j]
                    if k != 2: s += career[k]
                    if l != 2 : s += food[l]
                    d[s] = [-1]

    for info in infos:
        temp = info.split()
        dfs(temp, 0, '', d)


    d2 = {}
    
    # querys 최대 -> 100,000
    for query in querys:
        q = query.split()
        s=''
        if q[0] != '-' : s+=q[0]
        if q[2] != '-' : s+=q[2]
        if q[4] != '-' : s+=q[4]
        if q[6] != '-' : s+=q[6]
        
        if s not in d2:
            d[s].sort()
            d2[s] = True

        idx = bisect.bisect_left(d[s], int(q[7]))
        count = len(d[s]) -idx
        answer.append(count)

    return answer

 

후기

 

시간복잡도 때문에 처음에는 큰 틀을 바꿔야하는건가 고민했다. 접근방법이 아예 틀렸나..? 싶었는데 다행스럽게 그건 아니였다. 한줄 한줄을 잘 살펴보면서 어디서 최적화를 할 수 있는지 고민하다 보니 풀 수 있었다!

 

사실 중간에 아이디어가 너무 생각 안나서 질문들을 참고할까.. 위기가 있었는데, 시간박다보니 풀리더라. 뿌듯하다~