문제 링크

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

문제 설명

• 지원자의 (언어, 직군, 경력, 소울푸드, 점수) 가 주어진다
• 특정 조건을 만족하면서 특정 점수 이상인 지원자의 수 리턴

시도1

풀이

• 2중 for문으로 카운트
• O(N*M) 시간 초과
• 그냥 한 번 해봤다

코드

def solution(info, query):
    answer = []
    for q in query:
        언어1, _, 직군1, _, 경력1, _, 소울푸드1, 점수1 = q.split()
        점수1 = int(점수1)
        count = 0
        for i in info:
            언어2, 직군2, 경력2, 소울푸드2, 점수2 = i.split()
            점수2 = int(점수2)
            if 언어1 == '-' or 언어1 == 언어2:
                if 직군1 == '-' or 직군1 == 직군2:
                    if 경력1 =='-' or 경력1 == 경력2:
                        if 소울푸드1 == '-' or 소울푸드1 == 소울푸드2:
                            if 점수1 <= 점수2:
                                count += 1
        answer.append(count)
    return answer

시도2

풀이

• 딕셔너리에 조건에 따라 점수 저장
• 모든 조건을 순회하면서
• 쿼리가 '-'가 아니고, 일치하지 않는 경우 continue
• 점수 하나하나 카운트
• 시간복잡도가 개선됐다고 생각했으나 조건만 충족되도록 한 것 같다
• 이분 탐색 아이디어는 떠올랐으나 정렬 방법이 생각이 잘 안 났다
  • 힙? 최악의 경우 O(N) -> X
  • 정렬? O(NlogN) -> X

코드

list1 = ['cpp', 'java', 'python']
list2 = ['backend', 'frontend']
list3 = ['junior', 'senior']
list4 = ['pizza', 'chicken']


def solution(info, query):
    info_dict = get_info_dict(info)
    answer = get_count_list(info_dict, query)
    return answer


def get_info_dict(info):
    info_dict = {언어: {직군: {경력: {소울푸드: [] for 소울푸드 in list4} for 경력 in list3} for 직군 in list2} for 언어 in list1}
    for 점수, 언어, 직군, 경력, 소울푸드 in info:
        info_dict[언어][직군][경력][소울푸드].append(점수)
    return info_dict


def get_count_list(info_dict, query):
    count_list = []
    for q in query:
        언어, _, 직군, _, 경력, _, 소울푸드, 점수 = q.split()
        count = 0
        for k1 in list1:
            if not (언어 == '-' or k1 == 언어):
                continue
            for k2 in list2:
                if not (직군 == '-' or k2 == 직군):
                    continue
                for k3 in list3:
                    if not (경력 == '-' or k3 == 경력):
                        continue
                    for k4 in list4:
                        if not (소울푸드 == '-' or k4 == 소울푸드):
                            continue
                        for score in info_dict[k1][k2][k3][k4]:
                            if int(점수) <= score:
                                count += 1
        count_list.append(count)
    return count_list

시도3

풀이

• 처음부터 지원자를 점수에 따라 정렬시켜놓고 초기화 하면 정렬 가능
• 조건에 따라 돌면서
• bisect로 특정 점수 이상 지원자 수 카운트

코드

import bisect


list1 = ['cpp', 'java', 'python']
list2 = ['backend', 'frontend']
list3 = ['junior', 'senior']
list4 = ['pizza', 'chicken']


def solution(info, query):
    info_dict = get_info_dict(info)
    answer = get_count_list(info_dict, query)
    return answer


def get_info_dict(info):
    for i in range(len(info)):
        언어, 직군, 경력, 소울푸드, 점수 = info[i].split()
        info[i] = [int(점수), 언어, 직군, 경력, 소울푸드]
    info.sort()
    info_dict = {언어: {직군: {경력: {소울푸드: [] for 소울푸드 in list4} for 경력 in list3} for 직군 in list2} for 언어 in list1}
    for 점수, 언어, 직군, 경력, 소울푸드 in info:
        info_dict[언어][직군][경력][소울푸드].append(점수)
    return info_dict


def get_count_list(info_dict, query):
    count_list = []
    for q in query:
        언어, _, 직군, _, 경력, _, 소울푸드, 점수 = q.split()
        count = 0
        for k1 in list1:
            if not (언어 == '-' or k1 == 언어):
                continue
            for k2 in list2:
                if not (직군 == '-' or k2 == 직군):
                    continue
                for k3 in list3:
                    if not (경력 == '-' or k3 == 경력):
                        continue
                    for k4 in list4:
                        if not (소울푸드 == '-' or k4 == 소울푸드):
                            continue
                        count += len(info_dict[k1][k2][k3][k4]) - bisect.bisect_left(info_dict[k1][k2][k3][k4], int(점수))
        count_list.append(count)
    return count_list