[Programmers] 순위 검색
🎯 programmers > 2021 KAKAO BLIND RECRUITMENT > 순위 검색
🤔 나의 풀이
📌 문제
- programmers > 2021 KAKAO BLIND RECRUITMENT > 순위 검색
📌 날짜
2021.06.25
📌 시도 횟수
Failed
❌ 첫번째 시도 (정확성 100/효율성 0)
-
첫번째 풀이에서는 평소 우리가 구하는 방법 그대로 코드로 구현했다.
-
지원자 정보에서 조건을 차례대로 검사해나가면서, 조건을 만족하지 않는 경우는 다음 검색 대상에서 지워나가는 방식이다.
-
오답의 원인
- info 배열의 크기는 1~50000이다.
- query 배열의 크기는 1~100000이다.
- 이 방법은 매번 query의 각 조건을 검사할 때마다 info를 무조건 모두 검사해야 된다.
- 게다가 마지막 점수를 찾을 때에도 최악의 경우, 한번 더 모든 info를 검사해야된다.
- 그야말로 최악의 호율성!
❌ 두번째 시도 (정확성 100/효율성 0)
- 첫번째 시도에서
점수
를 찾는 과정을 이진 탐색을 사용했다. - 여전히 효율성에서
시간 초과
가 발생한다. - 단순히
점수
를 판별하는 과정을 이진 탐색으로 바꾸었다고 효율성이 통과되지는 않는다.
👊🏻 세번째 시도 (정확성 100/효율성 100)
- 결국 카카오 코딩테스트 해설을 참고했다. 물론 그래도 잘 이해가 안돼서 다른 분들의 코드도 참고해서 겨우 풀었다. (
이게 Lv2라니..)
⭐문제 해결 과정
- 각 info(지원자)에 대해 해당 조건을 만족할 수 있는 모든 경우를 구한다.
- 가능한 모든 경우는
available_cases
이라는 dict로 저장한다.available_cases
의 key 값은 info(지원자 정보) 중 [언어, 직군, 경력, 소울 푸드] 정보이다.available_cases
의 value 값은 해당 조건([언어, 직군, 경력, 소울 푸드])을 만족하는 info(지원자)들의점수
리스트이다.- 예를 들어,
“java backend junior pizza 150”
지원자의 경우 다음과 같이 16가지 그룹에 속하게 된다.
- 그리고 이렇게 구한 16가지 경우를, key값으로 사용하여 value에 현재 지원자의
점수
를 추가한다.- 이것을 모든 info에 대해 반복하여 구한다.
def add_available_cases(info): available_cases = defaultdict(list) for i in info: info_list = i.split() for a in (info_list[0], "-"): for b in (info_list[1], "-"): for c in (info_list[2], "-"): for d in (info_list[3], "-"): key = str(a + b + c + d) available_cases[key].append(int(info_list[-1])) return available_cases
- 이제 모든 준비가 끝났다! 지금부터는 query(조건)을 하나씩 돌면서,
available_cases
에서 key가 query(조건)일 때의 value를 가져온다.
available_cases
에서 key가 query(조건)일 때의 value는, query의 조건을 만족하는 모든 info(지원자)의점수
정보 리스트이다.- 이때 이 점수 리스트를
candidate_list
(후보자 리스트)라고 하자. '후보자'인 이유는 아직 마지막 조건인점수
조건은 검사하지 않았기 때문이다.점수
조건을 효율적으로 검사하기 위해서는두번째 시도
에서 언급한이진 탐색
의lower bound
(처음으로 k보다 같거나 큰 값)를 구하는 방법을 통해 구하면 효율성 측면에서 효과적으로 구할 수 있다.- 단, 이진 탐색을 구현하려면 먼저 숫자 리스트를 정렬 해주어야 한다.
# 숫자 리스트 정렬 def sort_available_cases(available_cases): for key, value in available_cases.items(): available_cases[key] = sorted(value) return available_cases # 이진 탐색으로 lower_bound 구해서 만족하는 경우 찾기 def lower_bound(candidate_list, key): result = 0 start, end = 0, len(candidate_list) while start < end: mid = (start + end) // 2 if candidate_list[mid] >= key: end = mid else: start = mid + 1 # 최종적으로 리턴하는 값은 lower_bound보다 큰 값의 개수이다. return len(candidate_list) - end
- 따라서 최종적으로
len(candidate_list) - end
를 리턴한다. 즉, 후보자들 중하한(OOO점 이상)
보다 크거나 같은 info(지원자)들이 몇 명인지 구해서 리턴한 것이다.
👏🏻 최종 코드
- 따라서 최종 코드는 다음과 같다 :D
import re
from itertools import combinations
from collections import defaultdict
def add_available_cases(info):
available_cases = defaultdict(list)
for i in info:
info_list = i.split()
for a in (info_list[0], "-"):
for b in (info_list[1], "-"):
for c in (info_list[2], "-"):
for d in (info_list[3], "-"):
key = str(a + b + c + d)
available_cases[key].append(int(info_list[-1]))
return available_cases
def sort_available_cases(available_cases):
for key, value in available_cases.items():
available_cases[key] = sorted(value)
return available_cases
def parse_query(query):
query_list = list(re.sub("and ", "", query).split())
return "".join(query_list[:-1]), int(query_list[-1])
def lower_bound(candidate_list, key):
result = 0
start, end = 0, len(candidate_list)
while start < end:
mid = (start + end) // 2
if candidate_list[mid] >= key:
end = mid
else:
start = mid + 1
return len(candidate_list) - end
def solution(info, queries):
available_cases = add_available_cases(info)
sorted_cases = sort_available_cases(available_cases)
answer = []
for query in queries:
query_list, query_num = parse_query(query)
candidate_list = available_cases[query_list]
answer.append(lower_bound(candidate_list, query_num))
return answer
🥺 느낀점
- 이게 Lv2라니..............ㅠ😭😭
- 정확성은 그럭저럭 풀겠는데...
효율성은 문제 해설 안 봤으면 못 풀었을 것 같다.. ㅠㅠ
Author And Source
이 문제에 관하여([Programmers] 순위 검색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@eunseokim/Programmers-순위-검색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)