[2021 KAKAO BLIND RECRUITMENT] 순위 검색

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

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

효율성 해결을 못해서 엄청 애먹었다. 삽질 엄청한듯

 

1) 삽질 1, re모듈사용

from itertools import product
import re
def make(p):
    temp = ''
    if p[0] == 'cpp': temp += '1'
    elif p[0] == 'java': temp += '2'
    elif p[0] == 'python': temp += '3'
    else: temp += '.'
        
    if p[1] == 'backend': temp += '1'
    elif p[1] == 'frontend': temp += '2'
    else: temp += '.'
        
    if p[2] == 'junior': temp += '1'
    elif p[2] == 'senior': temp += '2'
    else: temp += '.'
            
    if p[3] == 'chicken': temp += '1'
    elif p[3] == 'pizza': temp += '2'
    else: temp += '.'
    return temp

def solution(info, query):
    answer = []
    cases = []
    for i in info:
        p = i.split(' ')
        cases.append([make(p), p[4]])
    cases = sorted(cases, key = lambda x : (int(x[1])))
    patterns = []
    for i in query:
        p = i.split(' and ')
        p += ((p.pop(3)).split(' '))
        patterns.append([make(p), p[4]])
    for i in patterns:
        count = 0
        temp = []
        for j in range(len(cases)):
            if int(i[1]) <= int(cases[j][1]):
                temp = cases[j:]
                break
        for j in temp:
            if re.match(i[0], j[0]):
                count += 1
        answer.append(count)
    return answer

 

2) 삽질 2

def solution(infos, querys):
    answer = []
    ilist = []
    for i in infos:
        ilist.append(i.split(' '))
    ilist = sorted(ilist, key = lambda x : (int(x[4])))
    for i in querys:
        a = i.split(' and ')
        a += ((a.pop(3)).split(' '))
        temp = []
        for j in range(len(ilist)):
            if int(a[4]) <= int(ilist[j][4]):
                temp = ilist[j:]
                break
        count = 0
        for j in temp:
            if (a[0]=='-' or a[0]==j[0]) and (a[1]=='-' or a[1]==j[1]) and (a[2]=='-' or a[2]==j[2]) and (a[3]=='-' or a[3]==j[3]):
                count += 1
        answer.append(count)
    return answer

 

3) 삽질 3, 이분탐색 활용, 확실히 시간이 많이 줄었다, 그래도 효율성은 0점

def solution(infos, querys):
    answer = []
    ilist = []
    for i in infos:
        ilist.append(i.split(' '))
    for i in querys:
        a = i.split(' and ')
        a += ((a.pop(3)).split(' '))
        temp = []
        for j in ilist:
            if (a[0]=='-' or a[0]==j[0]) and (a[1]=='-' or a[1]==j[1]) 
            and (a[2]=='-' or a[2]==j[2]) and (a[3]=='-' or a[3]==j[3]):
                temp.append(int(j[4]))
        temp = sorted(temp)
        low = 0
        high = len(temp)
        while low!=high and low!=len(temp):
            if temp[(low+high)//2] >= int(a[4]):
                high = (low+high)//2
            else:
                low = (low+high)//2+1
        answer.append(len(temp)-low)
    return answer

 

---

 

결국 프로그래머스 다른 사람의 풀이 참고해서 풀이했다.

 

1. '-'를 포함한 모든 케이스 4*3*3*3=108에 대해 딕셔너리를 생성

2. 각 케이스를 key로 하는 튜플에 값(점수)를 리스트형태로 추가

3. 값(점수) 기준으로 초기화

4. 나머지는 위의 삽질했던 내용과 동일, 이분탐색을 활용해 구간 계산

def solution(info, query):
    data = {}
    #모든 케이스에 대해 딕셔너리 생성
    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), [])
    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()
        pool = data[(q[0], q[2], q[4], q[6])]
        find = int(q[7])
        l = 0
        r = len(pool)
        mid = 0
        while l < r:
            mid = (r+l)//2
            if pool[mid] >= find:
                r = mid
            else:
                l = mid+1
        answer.append(len(pool)-l)
    return answer