[프로그래머스] 2021 KAKAO BLIND RECRUITMENT - 순위 검색 (Python)

문제

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

프로그래머스

Level 2 이지만 굉장히 골치 아팠던 문제입니다.

---

코드 1

from collections import deque

def solution(info, query):
    answer = []
    dq = deque(info)
    info_lst = []
    new_info = []
    
    while dq:
        q = dq.popleft()
        info_lst.append(q)
        
    for i in info_lst:
        p = i.split(" ")
        new_info.append(p)
        
    for text in query:
        q = text.replace("and ", "").split(" ")
        print(q)
        ans = 0
        
        for x in new_info:
            cnt = 0
            
            for i in range(4):
                if q[i]=='-':
                    cnt += 1
                elif q[i]!=x[i]:
                    break
                else:
                    cnt += 1
                    
            if cnt==4:
                if int(q[4])<=int(x[4]):
                    ans += 1
                    
        answer.append(ans)
            
    return answer

별 다른 방법이 떠오르지 않아 일단 브루트포스로 풀어보았지만 바로 효율성 테스트에서 실패했다.

1 <= info <= 50,000

1 <= query <= 100,000

해당 조건때문에 대충 따져봐도 시간 복잡도는 O(c*n^2)이다. 최악의 경우 50억번의 연산을 수행해야 하기 때문에 효율성이 떨어질 수 밖에 없다.

풀이

일단 도저히 풀리지 않아 해설지를 참고해 풀었다 ...-_-

Key Point

1. 해당 조건에 따르면 query가 가질 수 있는 경우의 수는 총 4*3*3*3 = 108가지이며, info에 대한 값을 '-'을 포함해 미리 Dictionary[List]로 초기화한다.

2. 이분탐색

예를 들어, java backend junior pizza 150의 경우 key는 16가지의 경우의 수가 나오고, value는 score로 모든 경우의 수에 대해 score를 넣어 해시를 이용하는 Dictionary를 생성한다.

그리고 이분탐색을 하기 위해서 applicants[key]의 value들을 정렬해준다.

 

이분 탐색, Lower Bound, 그리고 Upper Bound

이분 탐색이 '원하는 값을 찾는 과정' 이라면 Lower Bound는 '원하는 값 이상이 처음 나오는 위치를 찾는 과정' 이며, Upper Bound는 '원하는 값을 초과한 값이 처음 나오는 위치를 찾는 과정'입니다.

우리는 특정 값 하나를 찾는 것이 아니라, 원하는 값 이상이 처음 나오는 위치를 찾아야 하기 때문에 Lower Bound를 이용했다.

Python의 bisect_left를 사용하면 더 간단하지만 직접 구현을 해보았다.

기존의 이분 탐색 코드와 크게 다르지 않다. 원래는 mid가 원하는 값에 해당하면 그 값을 return하면 된다.

Lower Bound의 경우, mid가 원하는 값 이상이라면 right = mid; else left = mid + 1를 반복해 반복문이 끝나면(left가 right보다 커지면) left를 return 해주어 원하는 값 중 최소 index를 뽑아주는 것이다.

코드 2

from collections import defaultdict
      
def binary_search(query, score):
    left, right = 0, len(query)
    
    if not right:
        return 0
    
    while left<right:
        mid = (left+right)//2
        
        if query[mid]>=score:
            right = mid
        else:
            left = mid + 1
            
    return left
        
        
def solution(infoes, queries):
    answer = []
    applicants = defaultdict(list)
    
    for info in infoes:
        info = info.split()
        
        for lang in [info[0], '-']:
            for job in [info[1], '-']:
                for career in [info[2], '-']:
                    for food in [info[3], '-']:
                        applicants[lang+job+career+food].append(int(info[4]))
    
    for key in applicants:
        applicants[key].sort()
    
    for query in queries:
        query = query.replace("and ", "").split()
        
        score = int(query[-1])
        query = "".join(query[:-1])
        
        left = binary_search(applicants[query], score)
        answer.append(len(applicants[query])-left)
        
    return answer