[프로그래머스] Lv.2 순위검색 - Python

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

코딩테스트 연습 - 순위 검색

---

• 생각
  • 정확성과 효율성을 모두 충족해야 함
    • 효율성의 점수가 더 큼
  • 정확성만
    1. 개발자가 원하는 조건을 한 글자로 만들기
       • "java and backend and junior and pizza 100" -> "javabackendjuniorpizza"
    2. 지원자의 점수가 개발자가 원하는 점수보다 높을 때
    3. 각 지원자의 정보로 만들 수 있는 모든 조건 중 1번과 일치하는 게 있는지 확인
       • "java backend junior pizza 150"
         • ''
         • 'java' , 'backend', 'junior', 'pizza'
         • 'javabackend', 'javajunior', 'javapizza', 'backendjunior', 'backendpizza', 'juniorpizza'
         • 'javabackendjunior', 'javabackendpizza', 'javajuniorpizza', 'backendjuniorpizza'
         • 'javabackendjuniorpizza'
    4. 모든 개발자가 원하는 조건 반복
  • 정확성 + 효율성
    1. 지원서에 입력한 4가지의 정보 경우 모두 dictionary의 key로 만들기
    2. 지원자의 점수를 1번 dictionary의 key에 해당하는 조건에 넣기
    3. 지원자들의 점수를 오름차순으로 정렬
    4. 개발자가 원하는 조건에 해당하며 원하는 점수 이상 만족하는 지원자 수 세기
       1. 지원자들의 점수가 오름차순으로 되어있으므로 이분탐색으로 찾기!!
• 코드1 (정확성만)

from itertools import combinations
import re

# 지원자의 가능
def person_case(person,q):
    for n in range(5):
        for com in combinations(person,n):
            k = "".join(com)
            if k == q:
                return True
    return False
        

def solution(info, query):
    answer = []
    for q in query:
        q = q.split(' ')
        score = int(q[-1])
        q = "".join(q[:-1])
        # 조건에 and와 - 부분 지우기
        q = re.sub('and','',q)
        q = re.sub('-','',q)
        cnt = 0
        for person in info:
            person = person.split(' ')
            s = int(person[-1])
            if score <= s:
                if person_case(person[:-1],q):
                    cnt += 1
        answer += [cnt]
            
    return answer

 

• 코드2 (정확성 효율성 둘다 통과)

# 지원자들 정보, 개발팀이 원하는 조건
def solution(info, query):
    # 나올 수 있는 모든 조건
    data = dict()
    for a in ['cpp', 'java', 'python', '-']:
        for b in ['backend', 'frontend', '-']:
            for c in ['junior', 'senior', '-']:
                for d in ['chicken', 'pizza', '-']:
                    data.setdefault((a, b, c, d), list())

    # 지원자들이 해당할 수 있는 조건에 점수 넣기
    for i in info:
        i = i.split()
        for a in [i[0], '-']:
            for b in [i[1], '-']:
                for c in [i[2], '-']:
                    for d in [i[3], '-']:
                        data[(a, b, c, d)].append(int(i[4]))

    # 지원자 점수 오름차순 정렬
    for k in data:
        data[k].sort()

    # 개발자가 원하는 조건에 맞는 인원 수
    answer = list()

    for q in query:
        q = q.split()
        # 개발자가 원하는 조건에 해당하는 사람들의 점수
        scores = data[(q[0], q[2], q[4], q[6])]
        # 개발자가 원하는 점수보다 높은 사람 수 세기 -> 이분 탐색
        wanted = int(q[7])
        l,r = 0, len(scores)
        while l < r:
            middle = (l + r)//2
            if scores[middle] >= wanted:
                r = middle
            else:
                l = middle + 1
        answer.append(len(scores)-l)
        
    return answer