[프로그래머스] 순위 검색 (Python 파이썬)

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

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

문제 설명

문제에 대한 설명이 굉장히 길어 링크로 대체합니다.

간단히 설명하자면, info에 있는 목록 중 query에 있는 목록을 만족하는 개수를 구하는 문제입니다.

---

풀이 과정

처음에는 딕셔너리와 이분탐색을 이용하지 않고, 주어진 리스트를 그대로 이용해

각 리스트 요소마다 하나씩 매번 검사하는 방법을 이용했습니다.

 

정확성은 통과를 했지만, 역시 효율성에서 실패했습니다.

 

방법 1

정확성 성공

효율성 실패

from itertools import combinations


def solution(info, query):
    answer = [0 for i in range(len(query))]
    infol = []
    queryl = []
    for i in range(len(info)):
        infol.append(info[i].split())
        # tmp = ['java', 'backend', 'junior', 'pizza', '150']
    for j in range(len(query)):
        queryl.append(query[j].split())
        while len(queryl[j]) > 5:
            queryl[j].remove("and")

    for i in range(len(infol)):
        for j in range(len(queryl)):
            flag = 0
            for k in range(4):
                if infol[i][k] != queryl[j][k]:
                    if queryl[j][k] != '-':
                        flag = 1
                        break
            if flag == 0:
                if int(infol[i][4]) >= int(queryl[j][4]):
                    answer[j] += 1

    return answer

 

효율성을 통과하기 위해 사용한 방법은,

딕셔너리(자바의 hash와 비슷한 파이썬의 자료구조), 이분탐색(BinarySearch)를 이용했습니다.

 

과정은 다음과 같습니다.

① info 안의 문자열을 공백을 기준으로 분리합니다. ( ex ['java', 'backend', 'junior', 'pizza', '150'] )

② 분리한 것 중, 앞의 4부분(java,backend..)을 키값으로, 마지막부분(150)을 value값으로 분리 합니다.

③ 키값들로 만들 수 있는 모든 조합을 생성합니다. (combinations 이용)

④ 이 조합으로 딕셔너리를 생성합니다. 해당 키값이 딕셔너리에 이미 존재하면 value값을 그 키의 value값에 추가합니다.    { 'javabackendjuniorpizza' : [150...] , 'java' : [100...] , ... } 식으로 생성이 되겠죠?

⑤ 딕셔너리의 각 원소마다 value값들을 기준으로 정렬합니다. [100,150,200...]식으로 되도록

 

⑥ query도 마찬가지로 분리합니다. ( query에는 and와 -도 있기 때문에 제거를 하여 info와 같은 형식으로 만듭니다. )

⑦ 이제 query를 한바퀴 돌면서, info딕셔너리를 탐방하게 되는데,

    query의 key값이 info딕셔너리의 키값으로 존재하면 그 info딕셔너리의 value값들을 가져옵니다.

⑧ 가져온 점수값에서 기준 점수값을 넘는 것들의 개수를 이분탐색을 통해 구하면 됩니다.

 

방법 2

정확성 성공

효율성 성공

from itertools import combinations
from bisect import bisect_left


def solution(info, query):
    answer = []
    info_dict = {}

    for i in range(len(info)):
        infol = info[i].split()  # info안의 문자열을 공백을 기준으로 분리
        mykey = infol[:-1]  # info의 점수제외부분을 key로 분류
        myval = infol[-1]  # info의 점수부분을 value로 분류

        for j in range(5):  # key들로 만들 수 있는 모든 조합 생성
            for c in combinations(mykey, j):
                tmp = ''.join(c)
                if tmp in info_dict:
                    info_dict[tmp].append(int(myval))  # 그 조합의 key값에 점수 추가
                else:
                    info_dict[tmp] = [int(myval)]

    for k in info_dict:
        info_dict[k].sort()  # dict안의 조합들을 점수순으로 정렬

    for qu in query:  # query도 마찬가지로 key와 value로 분리
        myqu = qu.split(' ')
        qu_key = myqu[:-1]
        qu_val = myqu[-1]

        while 'and' in qu_key:  # and 제거
            qu_key.remove('and')
        while '-' in qu_key:  # - 제거
            qu_key.remove('-')
        qu_key = ''.join(qu_key)  # dict의 key처럼 문자열로 변경

        if qu_key in info_dict:  # query의 key가 info_dict의 key로 존재하면
            scores = info_dict[qu_key]

            if scores:  # score리스트에 값이 존재하면
                enter = bisect_left(scores, int(qu_val))

                answer.append(len(scores) - enter)
        else:
            answer.append(0)

    return answer

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !