💻코딩테스트 문제풀이8

Chapter8. 이진 탐색

[문제30] 순위 검색 - Level2

지원자가 지원서에 입력한 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점 이상 받은 사람은 모두 몇 명인지를 의미
  • 각 단어는 공백문자(스페이스 바) 하나로 구분
  • ex) "cpp and - and senior and pizza 500"은 'cpp로 코딩 테스트를 봤으며, 경력은 senior이면서 소울푸드로 pizza를 선택한 지원자 중 코딩 테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?'를 의미

[문제풀이]

• 지원자는 주어진 4개의 선택지를 모두 골라야 하며, 성적과 함꼐 데이터가 저장된다.
• 코드로 구현할 사항은 주어진 데이터와 조건을 기반으로 결과를 추출하여 반환하는 것.

[코드작성]

• 지원자의 선택 사항과 점수가 담긴 문자열 배열, 데이터 조회 명령이 담긴 문자열 배열을 전처리

def solution(info, query):
	data = [i.split() for i in info]
    queries = []

for q in query:
	q = q.split()
    for _ in range(3): q.remove('and')
    queries.append(q)

• 문의별로 지원자의 데이터를 검사하여 조건에 맞는 정답을 찾는다.

answer = [0]

for i in range(len(queries)):
	q = queries[i]
    for info in data:
    	for j in range(5):
        	if q[j] == '-': continue
            elif j == 4 and int(info[j]) >= int(q[j]): answer[i] += 1
            elif info[j] != q[j]: break

• 기록된 정답 반환

return answer

[전체코드]

def solution(info, query):
	data = [i.split() for i in info]
    queries = []
    
    for q in query:
	q = q.split()
    for _ in range(3): q.remove('and')
    queries.append(q)
    
    answer = [0] * len(query)
    
    for i in range(len(queries)):
	q = queries[i]
    for info in data:
    	for j in range(5):
        	if q[j] == '-': continue
            elif j == 4 and int(info[j]) >= int(q[j]): answer[i] += 1
            elif info[j] != q[j]: break
            
 return answer

[다른 풀이]

• 미리 딕셔너리 데이터를 만들어놓은 변수 선언

from collections import defaultdict
def solution(info, query):
	answer = []
    people = defaultdict(list)

• 주어진 모든 지원자의 데이터를 for 문으로 순회하면서 가능한 경우의 수를 딕셔너리에 기록

from itertools import combinations

for i in info:
	person = i.split()
    score = int(person.pop())
    people[''.join(person)].append(score)
    
    for j in range(4):
    	case = list(combinations(person, j))
        for c in case:
        	people[''.join(c)].append(score)

• 기록한 딕셔너리의 성적 데이터를 모두 정렬

for i in people: people[i].sort()

• 문의 조건에 따라 검색하고, 나온 결과의 성적 배열을 이진 탐색하여 몇 명인지 확인

from bisect import bisect_left as left_bound

for i in query:
	key = i.split()
    score = int(key.pop())
    key = ''.join(key)
    key = key.replce('and', '').replace(' ', '').replace('-', '')
    answer.append(len(people[key]) - left_bound(people[key], score))
    
    return answer

[전체코드]

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

def solution(info, query):
	answer = []
    people = defaultdict(list)
    
    for i in info:
	person = i.split()
    score = int(person.pop())
    people[''.join(person)].append(score)
    
    for j in range(4):
    	case = list(combinations(person, j))
        for c in case:
        	people[''.join(c)].append(score)
            
    for i in people: people[i].sort()
    
    for i in query:
	key = i.split()
    score = int(key.pop())
    key = ''.join(key)
    key = key.replce('and', '').replace(' ', '').replace('-', '')
    answer.append(len(people[key]) - left_bound(people[key], score))
    
return answer