[Programmers]순위 검색

문제

문제 요약

Info

["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"]

 

Query

["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]

 

위와 같이 info와 qurey가 input으로 주어질 때, query의 기준에 해당되는 것이 몇개인지 구하는 문제이다.

Ex) cpp and - and senior and pizza 250 은 cpp이고, backend 혹은 frontend이면서, senior이고 pizza이고 250이상인 것

 

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

프로그래머스

---

 

풀이

 

풀이 1(효율성 0점)

하나 하나 비교하는 방법 효율성에서 시간초과가 발생한다.

def solution(info, query):
    answer = []
    
    for q in query:
        temp = 0
        criteria = q.replace('and', '').split()
        score = int(criteria.pop())
        
        for i in info:
            t = i.split()
            i_score = int(t.pop())

            if i_score >= score:
                for j in range(4):
                    if criteria[j] != '-' and t[j] != criteria[j]:
                        break
                else:
                    temp += 1
                    
        answer.append(temp)
    
    return answer

 

풀이2(이분 탐색)

 

1. 모든 경우를 딕셔너리로 만든다.

2. 각 경우에 해당하는 점수를 넣은 뒤, 이를 이분 탐색으로 개수를 찾는다.

 

처음 이분탐색을 써야한다는 걸 알았을 때, 'java', 'backend' 이런 문자열에 어떻게 이분탐새을 하라는 거지? ;; 이랬는데

이분탐색은 정렬된 숫자에서 가능하다는 걸 알면서도 이런 생각을 하고 있었다.ㅋㅋㅋㅋㅋㅋ

 

def binary_search(arr, target):
    lw = 0
    up = len(arr)
    
    while lw < up:
        mid = (lw+up)//2
        if arr[mid] >= target:
            up = mid
        else:
            lw = mid+1
            
    return lw

def solution(info, query):
    answer = []
    d = dict()
    
    for i in ['java', 'cpp', 'python', '-']:
        for ii in ['backend','frontend','-']:
            for iii in ['junior', 'senior', '-']:
                for iiii in ['chicken', 'pizza', '-']:
                    d[(i, ii, iii, iiii)] = []

    for i in info:
        l = i.split()
        score = int(l.pop())
        
        for j in [l[0], '-']:
            for jj in [l[1], '-']:
                for jjj in [l[2], '-']:
                    for jjjj in [l[3], '-']:
                        d[(j, jj, jjj, jjjj)].append(score)
    
    for key in d.keys():
        d[key].sort()
        
    for q in query:
        c = q.replace('and', '').split()
        arr = d[(c[0], c[1], c[2], c[3])]
        
        t = len(arr) - binary_search(arr, int(c[4]))
        answer.append(t)
                
    return answer