[프로그래머스] level2 순위 검색 (Python)

입력이 50,000이고, 쿼리가 100,000이다.

쿼리가 10만이라서 쿼리에 대한 답은 log 시간복잡도가 필요할거라고 감을 잡았다.

 

그리고 "java backend junior pizza 150" 

위와 같은 문자열이 들어오면

- and - and - and - 1000

- and - and - and pizza 1000

- and - and junior and - 1000 

...

이러한 쿼리의 답에 모두 속하게 된다

그래서 각 info마다 어떤 쿼리의 답이 될 지 모르기 때문에 모든 쿼리에 대한 경우의 수를 모두 구해야겠다고 생각했다.

 

_info = [i.split(' ') for i in info]
_query = []
for q in query:
    a = q.split(' and ')
    la = a[3].split(' ')
    na = ''.join([a[0], a[1], a[2], la[0]])
    num = int(la[1])
    _query.append((na, num))

위 코드를 통해 info와 query를 재구성하면

_info는 [["java", "backend", "junior", "pizza", "150"]] 이러한 배열로 변하고

_query는 [["java", "backend", "junior", "pizza", "100"]] 같은 배열로 변한다.

 

 

def dfs(n, info, nkey):
    global mydict
    
    if n == len(info) - 1:
        try:
            mydict[nkey].append(int(info[n]))
        except:
            mydict[nkey] = [int(info[n])];
        return
        
    dfs(n+1, info, nkey + info[n])
    dfs(n+1, info, nkey + '-')

각 _info의 원소(배열)을 가지고 백트래킹을 시도한다.

백트래킹을 할 때, 현재 인덱스의 값을 선택할지 말지를 정해서 key를 만들 수 있다.

따라서 'javabackendjuniorpizza' 이라는 문자열이 백트래킹을 통해서 만들어질 수 있고 'java-juniorpizza' 처럼 중간에 backend대신 '-'가 들어갈 수 있다.

현재 info 값이 어떤 쿼리에 속할 수 있는지 모두 확인하고, 속할 수 있는 쿼리가 key인 딕셔너리에 info값의 점수를 추가해준다. (배열 append)

 

global mydict
        
for k in mydict.keys():
    mydict[k].sort()

for q in _query:
    try:
        ins = bisect.bisect_left(mydict[q[0]], q[1])
        answer.append(len(mydict[q[0]]) - ins)
    except:
        answer.append(0)

 

딕셔너리의 key에 해당하는 모든 배열들을 오름차순 정렬한다.

그리고 쿼리를 key값으로 해서 해당 쿼리에 속하는 점수들의 배열을 찾을 수 있다.

점수 배열은 오름차순 정렬이 되어있고, 쿼리의 점수 이상인 점수들의 개수를 알아야 하므로 파이썬의 lower_bound를 사용해 해당 쿼리 점수 이상인 값의 개수를 알 수 있다.

 

 

전체 코드

import bisect

mydict = {}

def dfs(n, info, nkey):
    global mydict
    
    if n == len(info) - 1:
        try:
            mydict[nkey].append(int(info[n]))
        except:
            mydict[nkey] = [int(info[n])];
        return
        
    dfs(n+1, info, nkey + info[n])
    dfs(n+1, info, nkey + '-')
    

def solution(info, query):
    answer = []
    _info = [i.split(' ') for i in info]
    _query = []
    for q in query:
        a = q.split(' and ')
        la = a[3].split(' ')
        na = ''.join([a[0], a[1], a[2], la[0]])
        num = int(la[1])
        _query.append((na, num))
        
    for i in _info:
        dfs(0, i, "")
    
    global mydict
        
    for k in mydict.keys():
        mydict[k].sort()
    
    for q in _query:
        try:
            ins = bisect.bisect_left(mydict[q[0]], q[1])
            answer.append(len(mydict[q[0]]) - ins)
        except:
            answer.append(0)
    return answer