[프로그래머스] level2. 순위 검색- 파이썬

A. 문제설명

https://school.programmers.co.kr/learn/courses/30/lessons/72412?language=python3

 

 

각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return하라.

 

B. 답안

from itertools import product

def solution(info, query):
    answer = []
    a= list(product(["cpp","java","python",""],["backend", "frontend",""],["junior","senior",""],["chicken", "pizza",""]))
    a = [''.join(i) for i in a]
    d = {i:[] for i in a}
    
    for i in info:
        arr = i.split(' ')
        l= list(product([arr[0],''], [arr[1],''], [arr[2],''], [arr[3],'']))
        l = [''.join(j) for j in l]
        for j in l:
            d[j].append(int(arr[4]))
            
    for i in d.keys():
        d[i].sort()
    
    for q in query:
        q = q.replace(' and ', '').replace('-','')
        q = q.split(' ')
        
        val = binsearch(d[q[0]], int(q[1]))
        answer.append(len(d[q[0]])-val)
    
    # print(binsearch([1,4,6,9,15,20,36], 39))
    
    return answer

def binsearch(arr, val):
    if len(arr) == 0:
        return 0
    if arr[0] >= val:
        return 0
    start = 0
    end = len(arr)
    while start < end-1:
        mid = (start+end)//2
        if arr[mid] < val:
            start = mid
        else :
            end = mid
    return end

 

C. 회고 

소요시간 : 1시간 30분

 

이 문제는 다음과 같은 순서로 풀었다.

 

1.지원자 정보 기록할 수 있는 딕셔너리 생성 : 4x3x3x3 조합으로 .

2.지원자 정보 기록 : info 순회하며 조합생성하고 기록.

3.조건에 맞는 지원자 수 찾기: query순회하며.

4.지원자 수 효율적으로 찾기: 이분탐색 사용.

 

- 1, 2번은 product를 사용했다. 다만, info또한 조합을 구해서 정보를 기록해야한다는 걸 놓쳐서 좀 해맸다.

- 4번에서 좀 오래 걸렸다. 이분탐색을 스스로 구현해보았다. 디버깅해가면서 예외조건을 추가해 운 좋게통과했다. 하지만, 이분탐색을 완벽히 아는것이 아니어서 좀 더 이해가 필요하다. 특히, 예외처리(arr 길이가 0일 때, arr의 마지막 원소보다 찾으려는 값이 클 때)부분이 제일 까다로웠고, 이 부분은 디버깅이 아니었으면 찾기가 불가능했을 것이다.

 

그래도, 점차 실력이 좋아지고 있는걸 느낀다. '이렇게 풀면 되겠다'라고 떠오른 아이디어가 대부분 들어맞는다. 문제 유형의 패턴이 반복되어서 그런 듯 하다.

 

D. 개선

 

from itertools import product

def solution(info, query):
    answer = []
    #1.지원자 정보 기록할 수 있는 딕셔너리 생성 : 4x3x3x3 조합으로 
    a= list(product(["cpp","java","python",""],["backend", "frontend",""],["junior","senior",""],["chicken", "pizza",""]))
    d = {i:[] for i in a}
    
    #2.지원자 정보 기록
    for i in info:
        arr = i.split(' ')
        l= list(product([arr[0],''], [arr[1],''], [arr[2],''], [arr[3],'']))
        
        for j in l:
            d[j].append(int(arr[4]))
            
    for i in d.keys():
        d[i].sort()
    
    #3.조건에 맞는 지원자 수 찾기: query순회하며
    for q in query:
        q = q.replace(' and', '').replace('-','')
        q = tuple(q.split(' '))
        
        arr = d[q[0:4]]
        value = int(q[4])
        #4.지원자 수 효율적으로 찾기: 바이너리서치사용
        index = 0
        if len(arr) == 0:
            1==1
        elif arr[-1] < value:
            index = len(arr)
        else:
            index = binsearch(arr, int(q[4]), 0, len(arr)-1)
        
        answer.append(len(arr)-index)
        
    #디버깅용 print(binsearch([1, 3, 9, 9, 9, 11, 13, 15, 19, 21, 25, 28], 29, 0, 11))
        
    return answer

def binsearch(arr, score, left, right):
    if left == right:
        return left
    mid = (left+right)//2
    if arr[mid]<score:
        return binsearch(arr, score, mid+1, right)
    else:
        return binsearch(arr, score, left, mid)

 

1. 딕셔너리의 key값을 굳이 스트링으로 할 필요가 없었다. key값으로 불변값은 모두 가능하니, tuple을 사용하는게 코드가 더 간단해진다.

 

2. 바이너리 서치를 재귀식으로 구현했다. 코드가 더 간소해졌다. 이 부분은 어느정도 외우는게 필요해보인다.

 

3. 디버깅 해보면서 예외처리를 구현해 내는 과정에도 익숙해져야겠다.