프로그래머스 이진 탐색 문제입니다.

문제

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

개발언어, 지원직군, 지원경력, 소울푸드, 점수 등의 정보가 주어지고 해당하는 조건에 맞는 갯수를 세는 문제였습니다.

처음 시도할때 정보들의 항목을 수치로 변환하고 정렬한뒤에 이진 탐색을 통해 갯수를 판별하려고 하였습니다.🍋🍋🍋

[나의 풀이]

(실패)

def lowerbound(par_inf, q):

    start, end = 0, len(par_inf)

    # 점수를 제외한 조건만 판별
    for i in range(4):
		
        # "-" 일때
        if q[i] == -1:
            continue
        
        while start < end:
            mid = (start+end)//2
            
            if q[i] <= par_inf[mid][i]:
                end=mid
            else:
                start=mid+1
    print("start : ",start,", end :",end)

    return start

def upperbound(par_inf, q):

    start, end = 0, len(par_inf)
	
    # 점수를 제외한 조건만 판별
    for i in range(4):
		
        # "-" 일때
        if q[i] == -1:
            continue
        
        while start < end:
            mid = (start+end)//2
            if q[i] < par_inf[mid][i]:
                end=mid
            else:
                start=mid+1

    print("start : ",start,", end :",end)
    
    return start
    
def solution(info, query):
    answer = []

    # info 변환 Dict
    parser = {'-':-1,'cpp':0, 'java':1, 'python':2,
         'backend':0, 'frontend':1,
          'junior':0, 'senior':1,
          'chicken':0, 'pizza':1}

    par_inf = []

    # 변환
    for inf in info:
        
        inf = inf.split(" ")
        tmp_inf = []
        
        for i in range(4):
            tmp_inf.append(parser[inf[i]])
        tmp_inf.append(int(inf[-1]))

        par_inf.append(tmp_inf)

    # 이진 탐색 전 정렬
    par_inf = sorted(par_inf)

    print(par_inf)

    par_q = []

    # query 변환
    for q in query:
        q = q.replace("and","").split("  ")
        food_score = q[-1].split(" ")
        q[-1] = food_score[0]
        q.append(food_score[1])

        tmp_q = []

        for i in range(4):
            tmp_q.append(parser[q[i]])
        tmp_q.append(int(q[-1]))

        par_q.append(tmp_q)
    
    print(par_q)
	
    # query별 갯수 파악
    for q in par_q:
        print("-------------------------------")
        
        # 점수를 제외한 조건에 맞는 lower bound 파악
        left = lowerbound(par_inf,q)
        
        # 점수를 제외한 조건에 맞는 upper bound 파악
        right = upperbound(par_inf,q)
		
        # 점수를 제외한 조건에 맞는 info들만 추출
        tmp_inf = par_inf[left+1:right]

        print("tmp_inf : ",tmp_inf)
        print(" -- 점수 판별 --")
		
        # query에서 요구하는 점수 판별
        left , right = 0,len(tmp_inf)
        
        while left<right:
            
            mid = (left+right)//2
            print("left : ",left, " mid : ",mid, "right : ",right)
            if q[4] <= tmp_inf[mid][4] :
                right = mid
            else:
                if left < 0 :
                    break
                left = mid+1

        print("left : ",left," right : ",right)
		
        # 갯수 append
        answer.append(right+1-left)

    print(answer)
    return answer

위 코드에 경우

 query = ["python and frontend and senior and chicken 200"]

일때 정보들을 변환하고 정렬하여 아래와 같은 형태로 바꿔준 뒤

par_info = [[0, 0, 1, 1, 260], [1, 0, 0, 0, 80], [1, 0, 0, 1, 150], [2, 0, 1, 0, 50], [2, 1, 1, 0, 150], [2, 1, 1, 0, 210]]
query = [2, 1, 1, 0, 200]

개발언어, 지원직군, 지원경력, 소울푸드의 조건을 만족하는 정보들을 이진탐색을 통해 추출하면

tmp_inf :  [[2, 1, 1, 0, 150], [2, 1, 1, 0, 210]]

이고 다시 점수를 이진 탐색을 통해 판별하면

ans_inf :  [[2, 1, 1, 0, 210]]

위와 같이 나오게 됩니다.

하지만 "-" 조건(해당 조건 고려안함)이 있을 때는 제대로 작동하지 않습니다.
예를 들어

par_info = [[0, 0, 1, 1, 260], [1, 0, 0, 0, 80], [1, 0, 0, 1, 150], [2, 0, 1, 0, 50], [2, 1, 1, 0, 150], [2, 1, 1, 0, 210]]
query = [-1, 0, 1, -1, 150]

일때,

개발 언어 "-"인 조건을 통과한 후
지원직군이 0인 조건에 맞는 가장 안쪽, 바깥의 경계 left : 0 , right : 4

# 지원직군 조건까지 판별한 list
tmp_inf :  [[0, 0, 1, 1, 260], [1, 0, 0, 0, 80], [1, 0, 0, 1, 150], [2, 0, 1, 0, 50]]

지원경력이 1인 조건을 판별할 때 먼저 lower bound 파악 시 중간 인덱스 2의 info의 지원경력 값이 0으로 left = 4 ,
upper bound 파악 시 right = 4로

# 지원경력 조건까지 판별한 list
tmp_inf :  []

여러 요소를 가지고 있는 info들을 정렬함으로써 생긴 문제를 해결할 수 없었습니다. 이외에 딱히 다른 해결방안이 생각나지 않아 다른 풀이를 참고하게되었습니다.😰😰😰

[다른 사람의 풀이]

from itertools import combinations
from collections import defaultdict

def lower_bound(begin, end, target_list, target):
    if begin >= end:
        return begin    
    mid = (begin + end) // 2
    if target_list[mid] >= target:
        return lower_bound(begin, mid, target_list, target)
    else:
        return lower_bound(mid+1, end, target_list, target)

def solution(information, queries):
    answer = []
    dic = defaultdict(list)
    for info in information:
        info = info.split()
        
        # 조건
        condition = info[:-1]  
        
        # 점수
        score = int(info[-1])
        for i in range(5):
            case = list(combinations([0,1,2,3], i))
            for c in case:
                tmp = condition.copy()
                for idx in c:
                    tmp[idx] = "-"
                key = ''.join(tmp)
                dic[key].append(score)


    for value in dic.values():
        value.sort()   

    for query in queries:
        query = query.replace("and ", "")
        query = query.split()
        target_key = ''.join(query[:-1])
        target_score = int(query[-1])
        count = 0
        if target_key in dic:
            target_list = dic[target_key]
            idx = lower_bound(0, len(target_list), target_list, target_score)
            count = len(target_list) - idx
        answer.append(count)          
    return answer

위 풀이는 Dict를 통해 점수를 제외하고 "-"(상관없음)조건들을 모두 포함한 경우를 Key로 지정하고 해당하는 Key에 점수를 리스트 형태의 value값으로 넣는 형태였습니다. 🍑🍑🍑

모든 경우의 Key에 맞는 점수를 예시로 아래와 같은 형태였습니다.

{'javabackendjuniorpizza': [150], '-backendjuniorpizza': [150], 'java-juniorpizza': [150], 
'javabackend-pizza': [150], 'javabackendjunior-': [150, 80], '--juniorpizza': [150], 
'-backend-pizza': [150, 260], '-backendjunior-': [150, 80], 'java--pizza': [150], 
'java-junior-': [150, 80], 'javabackend--': [150, 80], '---pizza': [150, 260],
'--junior-': [150, 80], '-backend--': [150, 260, 80, 50], 'java---': [150, 80],
'----': [150, 210, 150, 260, 80, 50], 'pythonfrontendseniorchicken': [210, 150], 
'-frontendseniorchicken': [210, 150], 'python-seniorchicken': [210, 150, 50], 
'pythonfrontend-chicken': [210, 150], 'pythonfrontendsenior-': [210, 150],
'--seniorchicken': [210, 150, 50], '-frontend-chicken': [210, 150], '-frontendsenior-': [210, 150],
'python--chicken': [210, 150, 50], 'python-senior-': [210, 150, 50], 'pythonfrontend--': [210, 150], 
'---chicken': [210, 150, 80, 50], '--senior-': [210, 150, 260, 50], '-frontend--': [210, 150], 
'python---': [210, 150, 50], 'cppbackendseniorpizza': [260], '-backendseniorpizza': [260], 
'cpp-seniorpizza': [260], 'cppbackend-pizza': [260], 'cppbackendsenior-': [260],
'--seniorpizza': [260], '-backendsenior-': [260, 50], 'cpp--pizza': [260], 'cpp-senior-': [260],
'cppbackend--': [260], 'cpp---': [260], 'javabackendjuniorchicken': [80], 
'-backendjuniorchicken': [80], 'java-juniorchicken': [80], 'javabackend-chicken': [80], 
'--juniorchicken': [80], '-backend-chicken': [80, 50], 'java--chicken': [80], 
'pythonbackendseniorchicken': [50], '-backendseniorchicken': [50], 'pythonbackend-chicken': [50], 
'pythonbackendsenior-': [50], 'pythonbackend--': [50]}

모든 상황의 조건들을 구하기 위해 combination함수를 사용하였고 해당하는 조건의 점수list를 탐색하기 위해 이진 탐색을 사용하였습니다.

모든 경우의 조건을 Key로 생성하는 과정 자체에서 시간 초과가 나지 않을까 생각했지만 이후 조건에 맞는 점수를 찾는 과정에서 Key-value형태로 가져오는 방식으로 시간 단축하는 방식이었습니다.🐥🐥🐥

감사합니다.