[Programmers]2021 KAKAO BLIND RECRUITMENT: 순위 검색(Python)

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

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

꽤나 어려웠던 순위 검색 문제

쿼리문이 들어올 때 마다 SQL 문을 조합하여 실행하는 것은 시간초과에 걸리기 때문에

모든 SQL 경우에 대해 전처리를 해주어야 하는 문제였다

108개의 경우만 미리 처리해주면 된다

Python Code: 

def solution(info, query):
    answer = [0 for _ in range(len(query))]
    info=[i.split(' ') for i in info] # ' '공백 기준으로 잘라줌
    info.sort(key=lambda x:int(x[4]))   # 나중에 select 할 때 점수 순으로 이진탐색할거라서 미리 정렬해줌

    attr=[['-', 'cpp', 'java', 'python'], ['-', 'backend', 'frontend'], ['-', 'junior', 'senior'], ['-', 'chicken', 'pizza']]   #조합 테이블을 만들기 위한 어트리뷰트 테이블
    sample=[]
    for a in attr[0]:
        for b in attr[1]:
            for c in attr[2]:
                for d in attr[3]:
                    li=[[a,b,c,d]]
                    sample.append(li)   #모든 쿼리 가능한 경우의 수에 대해 테이블 만들어줌

    for i in range(len(sample)):
        sample[i].append([])
        for k in info:
            check=True
            for j in range(4):
                if sample[i][0][j]=='-':continue    #조건이 -일 경우에는 pass
                elif sample[i][0][j]!=k[j]:     #쿼리문과 맞지 않는 info이면 false
                    check=False
            if check:
                sample[i][-1].append(int(k[-1]))   
            # [['python', '-', 'senior', 'chicken'], [50, 150, 210]]
            # 이런 식으로 조건에 맞는 info의 점수를 미리 담아놓는 리스트 생성
    #미리 모든 select 쿼리에 맞는 지원자들 점수를 전처리해놓음
    #중복된 쿼리 수행이 매우 많을 수 있기 때문

    query=[q.split(' ') for q in query]
    query=[q[:1]+q[2:3]+q[4:5]+q[6:] for q in query]
    #쿼리문을 ' '와 and로 쪼개서 리스트에 담는다

    for q in range(len(query)): #이제 앞으로 들어오는 모든 쿼리에 대해 일치하는 지원자 수 카운트 할것
        for s in sample:    #미리 만든 샘플 테이블을 조회
            if query[q][:4] in s:   #만약 해당 쿼리문이 테이블에 있다면
                std=int(query[q][4])    #조회할 기준 점수
                left=0      #지원자가 50000이기 때문에 완탐으로 돌려본 결과 효율성에서 전부 시간초과남
                #그래서 미리 지원자들 점수를 sort해주었기 때문에 해당 기준 점수보다 높은 지원자의 숫자는 이진탐색으로 빠르게 구할 수 있음
                right=len(s[1])-1
                while left<=right:
                    mid=int((left+right)/2)
                    if s[1][mid]>=std:
                        right=mid-1
                    else: left=mid+1
                answer[q]=len(s[1])-right-1     #해당 점수 이상인 지원자의 숫자를 answer 리스트에 저장

    return answer

위의 코드와 같이 처음에 풀이했으나 더 pythonic하게 풀 수 있는 방법이 없을까 해서 계속해서 코드 리팩토링을 해주었다

def solution(info, query):
    answer = []
    info=[i.split(' ') for i in info]
    info.sort(key=lambda x:int(x[4]))

    dic={}
    for a in ['-', 'cpp', 'java', 'python']:
        for b in ['-', 'backend', 'frontend']:
            for c in ['-', 'junior', 'senior']:
                for d in ['-', 'chicken', 'pizza']:
                    dic[(a,b,c,d)]=[[a,b,c,d],[]]

    for key in dic:
        for k in info:
            check=True
            for j in range(4):
                if dic[key][0][j]=='-':continue
                elif dic[key][0][j]!=k[j]:check=False
            if check: dic[key][-1].append(int(k[-1]))

    for i in range(len(query)):
        q=query[i].split(' ')
        query[i]=((q[0],q[2],q[4],q[6]),int(q[7]))

    for (a,b) in query:
        s=dic[a]
        left=-1
        right=len(s[1])
        while left+1<right:
            mid=int((left+right)/2)
            if s[1][mid]>=b:
                right=mid
            else: left=mid
        answer.append(len(s[1])-right)

    return answer