[Programmers/Python] 순위 검색

유의했던 사항

1. 정확도와 효율성을 모두 만족해야 함

 

 

정확도(18/18), 효율성(0/4)

def solution(info, query):
    answer = []
    for q in query:
        q = q.replace('and', '')
        q = q.split()
        cnt = 0
        for i in info:
            i = i.split()
            flag = True
            if int(i[4]) < int(q[4]):
                flag = False
            else:
                for n in range(4):
                    if q[n] == '-':
                        continue
                    elif q[n] != i[n]:
                        flag = False
                        break

            if flag:
                cnt += 1
            
        answer.append(cnt)
            
    return answer

풀이과정 ( 효율성 통과 X )

1. query에 있는 'and'를 제거하기 위해 replace('and', '')를 사용해 query를 다시 만든다.

2. info에 있는 정보들을 공백을 기준으로 split해 각 지원자별로 정보를 다시 만든다.

3. 각 지원자별 점수가 query에 있는 점수보다 작으면 flag를 False로 바꾼다.

4. q[n] == '-' 일 때, continue

5. q[n] != i[n] 일 때, flag를 False

6. flag가 True일 때 cnt를 1 증가시키고 answer에 append

 

 

정확도(18/18), 효율성(4/4)

from itertools import combinations

def solution(info, query):
    answer = []
    db = {}
    
    for i in info:
        inf = i.split()
        # information는 조건들, 점수는 score에 따로
        information = inf[:-1]
        score = int(inf[-1])
        
        # itertools.combinations로 조합 구하기
        for n in range(5):
            comb = list(combinations([0, 1, 2, 3], n))
            for c in comb:
                nInfo = information.copy()
                for ni in c: # '-'를 포함해 새로운 조건
                    nInfo[ni]  = '-'
                cnInfo = '/'.join(nInfo)
                
                # 모든 조건을 딕셔너리로
                if cnInfo in db:
                    db[cnInfo].append(score)
                else:
                    db[cnInfo] = [score]
                    
    # 딕셔너리 내 모든 값 정렬 -> lower bound 알고리즘 사용하기 위해
    for v in db.values():
        v.sort()
        
    for q in query:
        qu = [i for i in q.split() if i != 'and']
        newQuery = '/'.join(qu[:-1])
        qScore = int(qu[-1])
        
        if newQuery in db:
            d = db[newQuery]
            if len(d) > 0:
                start, end = 0, len(d) # lower bound 알고리즘으로 인덱스를 찾아
                while start != end and start != len(d):
                    if d[(start+end) // 2] >= qScore:
                        end = (start + end) // 2
                    else:
                        start = (start + end) // 2 + 1
                answer.append(len(d) - start) # 그 인덱스~끝까지 개수를 answer에 append
                
        else:
            answer.append(0)
    return answer

잘 모르겠어서 여러 블로그와 자료들을 참고했다.....

위 풀이도 혼자 다시 해보라고 하면 못할 거 같음...

그래도 'lower bound'라는 새로운 알고리즘을 알게 됐으니 만족....^^

 

풀이과정(이라기보단 풀이법..)

-이분탐색을 이용(start, end 이용) → 원하는 값을 찾는 과정

-이 때 query에서 주어진 점수를 기준으로, info에 그 기준 점수보다 크거나 같은 점수를 가진 지원자를 찾아야 함

  → lower bound 이용

 

 

알게된 것

1. lower bound 알고리즘

- lower bound : 원하는 값 이상이 처음 나오는 위치를 찾음

- upper bound : 원하는 값 초과가 처음 나오는 위치를 찾음

※ bisect 라이브러리의 bisect_left가 lower bound와 같은 역할을 함