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

문제

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

프로그래머스

 

굉장히 간단해보이지만.. 효율성 테스트때문에 시간이 오래 걸렸던 문제!

---

 

주요 아이디어

처음에는 그냥 단순하게 비교만 하면 된다고 생각했다..!

• info, query를 공백 기준으로 split하고, 맨 끝의 score는 따로 배열을 만들어 넣었다
• query의 '-' 는 해당 조건은 보지 않겠다는 뜻이므로 가능한 경우의 수를 다 집어넣었다

 

---

 

코드 구현 (Python 3)

 

def solution(info, query):
    
    answer = []
    
    # info 끊어서 저장
    info_list = [x.split() for x in info]
    
    info_score = [int(x[-1]) for x in info_list]
    info_list = [x[:-1] for x in info_list]
    
    # query도 끊어서
    query_list = [x.split(' and ') for x in query]
    
    # '-' 대체용
    total_dict = {"0" : ["cpp", "java", "python"], "1" : ["backend", "frontend"], 
                  "2" : ["junior", "senior"], "3" : ["chicken", "pizza"]}
    
    for idx, q in enumerate(query_list):
        query_list[idx] = q[:-1] + q[-1].split(' ')
    
    query_score = [int(x[-1]) for x in query_list]
    query_list = [x[:-1] for x in query_list]

    for q in range(len(query_list)):
        for i in range(len(query_list[q])):
            if query_list[q][i] == '-':
                query_list[q].extend(total_dict[str(i)])

    # 비교
    for idx, q in enumerate(query_list):
        cnt = 0
        for i, info in enumerate(info_list):
            if set(info).issubset(set(q)) and info_score[i] >= query_score[idx]:
                cnt += 1
        answer.append(cnt)
        
    return answer

 

 

테스트 케이스는 통과했으나 효율성 테스트에서 여지 없이 실패..ㅠㅠ

---

 

실패 원인

실패 원인과 정확한 솔루션을 알아보고자 해당 서적을 참고했다.

• info 배열의 크기는 최대 50,000이다
• query 배열의 크기는 최대 100,000 이다
• 따라서 하나씩 대조하는 방법으로 한다면, 최대 50,000 * 100,000 = 50억의 반복횟수가 된다!

이렇듯 효율성을 체크하는 문제에서는 O(n^2) 시간 복잡도가 나온다면 다시 푸는 것이 방법일 것 같다..

 

비교 탐색을 반드시 수행해야 하는데 양이 많은 경우 이분 탐색을 활용하자!

 

• 주어진 조건에서 가능한 모든 조합을 생각해보자

예시 1. java, backend, junior, pizza를 만족시키는 모든 문의 조건

java	backend	junior	pizza
-	backend	junior	pizza
java	-	junior	pizza
java	backend	-	pizza
java	backend	junior	-
-	-	junior	pizza
-	backend	-	pizza
-	backend	junior	-
java	-	-	pizza
java	-	junior	-
java	backend	-	-
-	-	-	pizza
-	-	junior	-
-	backend	-	-
java	-	-	-
-	-	-	pizza
-	-	-	-

하나의 지원자 조건에 해당하는 문의 조건은 총 16가지

미리 선택 가능한 사항별로 경우의 수를 구하면 단순 조회만으로 결과를 알아낼 수 있다!

-> 모든 경우의 수를 딕셔너리 자료형으로 만들어 O(1) 시간 안에 확인 가능하도록 하자

 

그러니까 조건에 맞는 -> 지원자를 탐색하는 것이 아니라

해당 지원자가 가능한 경우의 수를 만들어놓고 -> 이에 맞는 조건을 찾는 것이다!

• defaultdict를 통해 "지원자 조건" : [점수] 형태로 딕셔너리를 구성한다
  
  • 이 때 "-" 를 고려해서 모든 경우의 수를 형성한다
  • 공백을 모두 제거하고 concat해 문자열 형태로 key를 만든다
• 점수를 기준으로 정렬한다
• query 문을 순회하며 조건에 해당하는 것들 중, 테스트 score에 미달하는 것들만 제거해 길이를 반환한다
  • bisect_left 함수를 통해 점수 하한선을 구할 수 있다

 

 

---

코드 재구현 (Python 3)

 

 

 

---

 

제출 결과

from itertools import combinations
from collections import defaultdict
from bisect import bisect_left

def solution(info, query):
    answer = []
    
    # 지원자 info를 돌면서 가능한 경우의 수를 모두 만들어보자
    applicants = defaultdict(list)
    
    for i in info:
        applicant = i.split()
        score = int(applicant.pop()) # 점수는 따로 분리해주기
        
        # 해당 조건에 해당하는 모든 지원자의 점수를 value로 append
        applicants[''.join(applicant)].append(score)
        
        # 모든 경우의 수 만들어내기
        for j in range(4):
            candi = list(combinations(applicant, j))
            for c in candi:
                applicants[''.join(c)].append(score)
    
    # 정렬하기
    for i in applicants:
        applicants[i].sort()
    
    for i in query:
        key = i.split()
        score = int(key.pop())
        
        key = ''.join(key)
        key = key.replace('and', '').replace(' ', '').replace('-', '')
        answer.append(len(applicants[key]) - bisect_left(applicants[key], score))
    
    return answer

 

 

---

 

코드 개선 방안

효율성 테스트가 있는 문제에서는 시간 복잡도를 꼭 체크하자!