[문제 풀이] 순위 검색

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

해결 과정

정확성 40 + 효율성 60 인 문제. 정확성만 따지고 풀었을 때 효율성은 0점이 나왔다. 효율성을 어떻게 낼지 감이 안와서 카카오 코테 설명란을 보고 이해하고 스스로 풀기로 함. 아니 근데 이거 이해하는 것 자체도 시간이 걸렸다. 어쨌든 dictionary 자료구조만 이용하고, 이진탐색 안쓰면 역시나 효율성 0점이 나온다. 이진탐색 써서 풀어보면 효율성 잘나옴 ㅋ O(n)의 시간을 O(logN)으로 바꾸는 탐색.. 오케이.

나의 풀이

1. 정확성 40 효율성 0

정확성만 겨냥한다면 쉽게 풀 수 있는 문제. 하지만 매 query 마다 info를 탐색하도록 하면 효율성 테스트는 모두 실패한다.

def solution(info, query):
    answer = []
    for curQuery in query:
        curList = curQuery.split()
        curQueryList = [curList[0], curList[2], curList[4], curList[6], curList[7]]
        tempNum = 0
        for curInfo in info:
            curInfoList = curInfo.split()
            for a, b in zip(curQueryList, curInfoList):
                if a.isdigit() and int(a) <= int(b):
                    tempNum += 1
                else:
                    if a == "-":
                        continue
                    else:
                        if a != b:
                            break
        answer.append(tempNum)       
    return answer

2. 정확성 40 효율성 0 (dictionary로 구조 변경)

dic을 아예 새로 정의한 뒤, 이진탐색 안쓰고 풀었을 때

from itertools import product


def solution(info, query):
    answer = []
    dic = {}
    # info 에 대해서 필요한 자료구조 (dic) 만들어 두기
    for element in info:
        tempList = element.split()
        infoList = tempList[:4]
        score = int(tempList[4])

        items = [[a, b] for a, b in zip(infoList, ["-"] * 4)]

        for i in list(product(*items)):
            key = "".join(i)
            if key not in dic:
                dic[key] = []
            dic[key].append(score)

    for element in query:
        tempList = element.split()
        key = "".join([tempList[0], tempList[2], tempList[4], tempList[6]])
        score = int(tempList[7])

        if key in dic:
            answer.append(len([x for x in dic[key] if x >= score]))
        else:
            answer.append(0)

    return answer

3. 정확성 40, 효율성 60 (dictionary + 이진탐색)

아니 근데... 여기서 완전 헤맨게, 이진탐색을 위한 sort() 해주는 걸 for 문 안에서 이중 for 문으로 해주고 있었음;;;;;;;;;;;;;;;;;;; 나중에라도 발견해서 다행 ㅋ

from itertools import product
from bisect import bisect_left

def solution(info, query):
    answer = []
    dic = {}
    # info 에 대해서 필요한 자료구조 (dic) 만들어 두기
    for element in info:
        tempList = element.split()
        infoList = tempList[:4]
        score = int(tempList[4])

        items = [[a, b] for a, b in zip(infoList, ["-"] * 4)]

        for i in list(product(*items)):
            key = "".join(i)
            if key not in dic:
                dic[key] = []
            dic[key].append(score)

    for value in dic.values():
        value.sort()

    for element in query:
        tempList = element.split()
        key = "".join([tempList[0], tempList[2], tempList[4], tempList[6]])
        score = int(tempList[7])

        if key in dic:
            index = bisect_left(dic[key], score)
            answer.append(len(dic[key]) - index)
        else:
            answer.append(0)

    return answer

다른 풀이

 

 

IDEA

시간복잡도.

https://www.bigocheatsheet.com/

query 10만 개, info 5만 개면 비교가 50억 번인데 안될 것 같네요.

처음 짠 코드는 len(query) -> m, len(info) -> n이라고 할 때, O(mn)이 나온다. 즉, 매 query를 살필 때 마다 매 info를 살피는건 비효율적인 구조라는 것. 아니 근데 풀이 아이디어.. 기발하네. 애초에 다음과 같은 구조를 생각해내는게 포인트인듯... 다음과 같은 구조를 한 번 만들어두고 매 query를 볼 때마다 이미 만들어진 다음 구조에서 개수 세면 됨.

위 코드에서 dic을 출력하면 다음과 같다. (예시임)

{
   "javabackendjuniorpizza":[
      150
   ],
   "javabackendjunior-":[
      80,
      150
   ],
   "javabackend-pizza":[
      150
   ],
   "javabackend--":[
      80,
      150
   ],
   "java-juniorpizza":[
      150
   ],
   "java-junior-":[
      80,
      150
   ],
   "java--pizza":[
      150
   ],
   "java---":[
      80,
      150
   ],
   "-backendjuniorpizza":[
      150
   ],
   "-backendjunior-":[
      80,
      150
   ],
   "-backend-pizza":[
      150,
      260
   ],
   "-backend--":[
      50,
      80,
      150,
      260
   ],
   "--juniorpizza":[
      150
   ],
   "--junior-":[
      80,
      150
   ],
   "---pizza":[
      150,
      260
   ],
   "----":[
      50,
      80,
      150,
      150,
      210,
      260
   ],
   "pythonfrontendseniorchicken":[
      150,
      210
   ],
   "pythonfrontendsenior-":[
      150,
      210
   ],
   "pythonfrontend-chicken":[
      150,
      210
   ],
   "pythonfrontend--":[
      150,
      210
   ],
   "python-seniorchicken":[
      50,
      150,
      210
   ],
   "python-senior-":[
      50,
      150,
      210
   ],
   "python--chicken":[
      50,
      150,
      210
   ],
   "python---":[
      50,
      150,
      210
   ],
   "-frontendseniorchicken":[
      150,
      210
   ],
   "-frontendsenior-":[
      150,
      210
   ],
   "-frontend-chicken":[
      150,
      210
   ],
   "-frontend--":[
      150,
      210
   ],
   "--seniorchicken":[
      50,
      150,
      210
   ],
   "--senior-":[
      50,
      150,
      210,
      260
   ],
   "---chicken":[
      50,
      80,
      150,
      210
   ],
   "cppbackendseniorpizza":[
      260
   ],
   "cppbackendsenior-":[
      260
   ],
   "cppbackend-pizza":[
      260
   ],
   "cppbackend--":[
      260
   ],
   "cpp-seniorpizza":[
      260
   ],
   "cpp-senior-":[
      260
   ],
   "cpp--pizza":[
      260
   ],
   "cpp---":[
      260
   ],
   "-backendseniorpizza":[
      260
   ],
   "-backendsenior-":[
      50,
      260
   ],
   "--seniorpizza":[
      260
   ],
   "javabackendjuniorchicken":[
      80
   ],
   "javabackend-chicken":[
      80
   ],
   "java-juniorchicken":[
      80
   ],
   "java--chicken":[
      80
   ],
   "-backendjuniorchicken":[
      80
   ],
   "-backend-chicken":[
      50,
      80
   ],
   "--juniorchicken":[
      80
   ],
   "pythonbackendseniorchicken":[
      50
   ],
   "pythonbackendsenior-":[
      50
   ],
   "pythonbackend-chicken":[
      50
   ],
   "pythonbackend--":[
      50
   ],
   "-backendseniorchicken":[
      50
   ]
}

 

binary search / 이진 탐색

머릿속에 흐릿하게 남아있던 이진 탐색. O(n)의 시간도 많아서 O(logN)으로 줄일 수 있는 탐색이다. 대신, 오름차순 정렬이 되어있어야 한다. 이 문제에서도 순차 탐색을 활용하면 효율성 못 내게 되어 있다. 

파이썬에서는 내장으로 bisect이 존재한다. 위 코드에선 bisect.bisect_left를 활용했다. 

 

defaultdict() 활용

말 그대로 default 값을 명시해주는 dictionary 이다. 가끔씩 defaultdict() 가 나오는 걸 봤는데, 이런 곳에서 활용할 수 있는거였네.

dic = defaultdict(list) 해주면 위 코드가 더 깔끔해짐. key 가 없는지 여부를 확인해서 빈 리스트를 할당해줘야 했는데 이럴 필요 없이 list가 기본 value 값이니, 바로 .append() 가능.

 

itertools의 product

두 개 이상 리스트에서 조합 구할 때. 위에서도 활용했다. 다른 풀이에서 key 값을 구하는 방식 보다 조금 더 직관적으로 생각할 수 있음. 

[['java', '-'], ['backend', '-'], ['junior', '-'], ['pizza', '-']] 각 원소 별로 하나씩만 뽑을 수 있음.