[프로그래머스] 순위 검색

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

프로그래머스

 

[문제]

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로
구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

---

[제한사항]

info 배열의 크기는 1 이상 50,000 이하입니다.
info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
개발언어는 cpp, java, python 중 하나입니다.
직군은 backend, frontend 중 하나입니다.
경력은 junior, senior 중 하나입니다.
소울푸드는 chicken, pizza 중 하나입니다.
점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
query 배열의 크기는 1 이상 100,000 이하입니다.
query의 각 문자열은 "[조건] X" 형식입니다.
[조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
언어는 cpp, java, python, - 중 하나입니다.
직군은 backend, frontend, - 중 하나입니다.
경력은 junior, senior, - 중 하나입니다.
소울푸드는 chicken, pizza, - 중 하나입니다.
'-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

---

문제 조건을 보면 info가 최대 50,000, query는 최대 100,000이다.

query에서 info를 접근하면 100,000 * 50,000 으로 5억.. 무조건 시간복잡도에서 걸린다.

일단 info와 query를 따로 처리해야하고, 자료형을 어떻게 구상할지도 생각해야한다.

 

자료형은 리스트 아니면 딕셔너리인데, 무조건 딕셔너리지.

해시테이블은 검색에선 짱짱맨이다 O(1)로 검색할 수 있으니깐.

 

info_dict = {
            "cpp":set(),
            "java":set(),
            "python":set(),
            "backend":set(),
            "frontend":set(),
            "junior":set(),
            "senior":set(),
            "chicken":set(),
            "pizza":set(),
            "-":set()
            }
score = []
for idx,i in enumerate(info):
    language,position,proficiency,food,num = i.split()
    arr = [language,position,proficiency,food]
    for j in arr:
        info_dict[j].add(idx)
    info_dict["-"].add(idx)
    score.append(int(num))

처음엔 위처럼 인덱스를 저장한 집합을 벨류로 하는 딕셔너리+점수 리스트를 구상하고

교집합을 구해봤는데 답은 나오지만 시간초과로 실패.

더 효율적으로 코드를 짜야한다.

생각해보니 info_dict에서 key값을 저렇게 나누지말고

 

1. info에서 주어지는 값 자체로 key를 구상하고 value를 점수를 포함하는 리스트로 하는게 더 좋을거같다 !

2. value값인 리스트를 오름차순으로 정렬

3. bisect_left 함수를 사용해서 이진탐색으로 시간절약 + 인덱스 찾으면 될 듯 !

 

바로 코드를 짜 보았다.

 

from collections import defaultdict
from bisect import bisect_left

def info_process(info):
    info_dict = defaultdict(list)
    for i in info:
        language,position,proficiency,food,num = i.split()
        key = f'{language}_{position}_{proficiency}_{food}'
        info_dict[key].append(int(num))
    for key in info_dict:
        info_dict[key].sort()
    return info_dict
    
def solution(info, query):
    info_dict = info_process(info)
    answer = []
    for q in query:
        language,position,proficiency,food = q.split(' and ')
        food, num = food.split()
        num = int(num)

        languages = [language] if language != '-' else ["cpp", "java", "python"]
        positions = [position] if position != '-' else ["backend", "frontend"]
        proficiencies = [proficiency] if proficiency != '-' else ["junior", "senior"]
        foods = [food] if food != '-' else ["chicken", "pizza"]
        
        count = 0
        for lang in languages:
            for pos in positions:
                for prof in proficiencies:
                    for fd in foods:
                        key = f'{lang}_{pos}_{prof}_{fd}'
                        score = info_dict[key]
                        count += len(score) - bisect_left(score, num)
        answer.append(count)
    return answer

깔끔하게 클리어 !

 

ps.

생각을 정리하고 코드를 짜니 큰 문제없이 풀 수 있었다.

사소하지만 추가로 고민했던 부분이 있는데

# 1
languages = [language] if language != '-' else ["cpp", "java", "python"]

# 2
languages = ["cpp", "java", "python"] if language == '-' else [language]

#1과 #2는 같은 동작을 하는 코드인데 어떤 코드가 보기 편할까를 고민했다.

사람마다 다를 순 있지만 나는 #1이 더 보기 편하다고 생각했다.

default는 language고 특이점이 else에 위치하는 것이 눈에 확 들어온다.

이런것도 컨벤션이 있으려나? 나중에 개발자가 된다면 사수한테 물어봐야겠다.