[카카오][Python] 순위검색 - combination 그리고 이진탐색

아래의 문제는 카카오 채용 코딩테스트 내용이며 코드는 직접 푼 내용입니다.

---

순위검색 

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

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

문제상황

 

요구사항

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

입출력

---

풀이과정-실패방법

처음부터 조합을 생각하지 못했었다...!

그래도 처음 info를 dict로 만드려는 시도는 좋았다. 하지만 key와 value를 잘못잡았다...

{'언어': ['java', 'python', 'python', 'cpp', 'java', 'python'],

'직군': ['backend', 'frontend', 'frontend', 'backend', 'backend', 'backend'], 

이렇게 생각하고,  단순히 if문으로 뽑으려고 했는데

그럼 조건에 해당하는 인덱스? 그 사람을 어떻게 뽑을지가 의문이였다.

그래서 이 방법이 아닌 해설을 보고 다시 이해보았다. 

 

풀이과정-해결방법

일단 3가지로 볼 수 있다. 

1. info 정리하는 부분

2. query 정리하는 부분

3. 쿼리결과를 찾는 부분 (이진탐색)

 

1. info 정리하는 부분

일단 내가 했던 방향대로 dict를 만드는건 맞다. 그래서 defatuldict를 사용했다. dict에 들어갈 value의 타입은 list이다.

이때 key는 키워드로 만들수 있는 조합이 들어가야한다.!! 그리고 value는 그 경우에 해당하는 점수이다. 

그래서 key, value로 만든 dict는 예를 들면 이런식이다. ex : {'':[전부], 'java':[80,150],.. 'javapizza':[150].....}

아무것도 안뽑았을때에 해당하는 조합엔 모든 점수가 들어가고, 

java하나만 뽑았을땐, 그때 해당하는 점수, javapizza를 두개뽑았을땐 그때 해당하는 점수 쭉쭉이다.

 

그래서 코드랑 디버깅한 내용으로 이해해보면 아래와 같다.

조합을 만들 데이터들은 info_keylist가 된다. 그리고 점수는 inf_value

    #1.info가지고 dict생성
    for i in info:
        row=i.split()
        info_keylist=row[:-1] #그외의 내용 : key가 될 후보
        info_value=int(row[-1]) #점수
        print("1.1 info_keylist",info_keylist," info_value",info_value)

키워드로 만들 수 있는 조합으로 key를 만들고, info_dict생성(점수값을 기준으로 오름차순 생성)

info_dict를 정렬하는 이유는 이후에 score에 해당하는 값을 찾아내는데 시간을 줄이기 위해서이다. 

        #1.1 하나의info에 대한 경우의수 16개 = key
        for i in range(5):
            for c in combinations(info_keylist,i):
                #print(c) #1개선택, 2개선택,3개선택,.... 모두다 선택될 경우
                info_key = ''.join(c)
                #print(tmp_key)
                info_dict[info_key].append(info_value) #하나의info에 대한 가능한 경우를 key, 점수를 value

    #1.2 점수값들을 오름차순정렬 (이후 이분탐색을 위해)
    for key in info_dict.keys():
        info_dict[key].sort()
    print()
    print(info_dict)
    print()

 

 

info_dict는 이렇다.

 

2. query 정리하는 부분

info와 마찬가지로 key가 될 후보들을 query에 넣고, 점수는 query_score로 지정했다. 

그리고 몇가지 처리를 해주었다. and를 제거해준다던지, -를 제거해준다던지..

    #2.query정리
    for q in query:
        qrow=q.split(' ')
        query_score=int(qrow[-1]) #점수
        query=qrow[:-1] #그외의 내용 : key가 될 후보

        #2.1 query_keylist처리 : and 제거
        for _ in range(3):
            query.remove('and')
        #2.2 query_keylist처리 : - 제거
        while '-' in query:
            query.remove('-')
        query_key = ''.join(query)
        print("2.1 query_key", query_key," query_score",query_score)

그러면 query_key와 query_score로 정리가 된다.

이제 query_key를 가지고 dict에서 select같이 찾아주면 scoreList가 그 결과로 나온다. 

3. 쿼리결과를 찾는 부분 (이진탐색)

이제 우리의 문제였던 " 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return " 할 준비가 된것이다.

사실 전체 쿼리결과에서 일일이 query_score 보다 큰 값이 어디에 있는지 찾아도 되지만

이 문제는 효율성도 검사하기 때문에 조금더 빠른 이진탐색을 이용할 수 있다. 

 

이진탐색은 간단히 말하면 절반씩 나눠서 query_score 보다 큰 값이 있는지 확인해보고,

없으면 그 값을 기준으로 더 큰값의 범위에서 검색하고,

있으면 그 값을 기준으로 더 작은값의 범위에서 검색하는 것이다.

 

그래서 그 구하고자 하는 값의 위치는 전체길이-시작위치가 된다.

 

아 그리고 예외처리로, 만약에 문의조건에 해당하는 사람이 아예 없다면 0을 출력하게 된다. 

        #3.lower bound사용해 query_score 보다 큰 점수들의 개수를 구하기
        #3-1.쿼리에 해당하는 score 찾음
        if query_key in info_dict:
             scoreList = info_dict[query_key] #dict에서 키워드에 해당하는 score 뽑음
             print("3.1 select result", scoreList)
             print()

             #3-2.socre보다 큰 점수들의 개수를 세는 방법 : 이분탐색
             if len(scoreList)>0:
                 start=0
                 end=len(scoreList)
                 while start< end:
                     mid=(start+end) //2
                     if scoreList[mid] >= query_score:
                         end = mid
                     else:
                         start = mid+1
                 answer.append(len(scoreList)-start)

        #3-1.쿼리에 해당하는 score가 없을때
        else:
            answer.append(0)

    return answer

 

 

결과

내가 나름 이해하면서 작성한 주석까지 포함한다.

from collections import defaultdict
from itertools import combinations

def solution(info, query):
    answer = []
    info_dict=defaultdict(list)
    #{키워드로 만들수 있는 조합 : [그 경우에 해당하는 점수들]}
    #ex : {'java':[80,150],.. 'javapizza':[150].....'-':[전부]}

    #1.info가지고 dict생성
    for i in info:
        row=i.split()
        info_keylist=row[:-1] #그외의 내용 : key가 될 후보
        info_value=int(row[-1]) #점수
        print("1.1 info_keylist",info_keylist," info_value",info_value)

        #1.1 하나의info에 대한 경우의수 16개 = key
        for i in range(5):
            for c in combinations(info_keylist,i):
                #print(c) #1개선택, 2개선택,3개선택,.... 모두다 선택될 경우
                info_key = ''.join(c)
                #print(tmp_key)
                info_dict[info_key].append(info_value) #하나의info에 대한 가능한 경우를 key, 점수를 value

    #1.2 점수값들을 오름차순정렬 (이후 이분탐색을 위해)
    for key in info_dict.keys():
        info_dict[key].sort()
    print()
    print(info_dict)
    print()

    #2.query정리
    for q in query:
        qrow=q.split(' ')
        query_score=int(qrow[-1]) #점수
        query=qrow[:-1] #그외의 내용 : key가 될 후보

        #2.1 query_keylist처리 : and 제거
        for _ in range(3):
            query.remove('and')
        #2.2 query_keylist처리 : - 제거
        while '-' in query:
            query.remove('-')
        query_key = ''.join(query)
        print("2.1 query_key", query_key," query_score",query_score)

        #3.lower bound사용해 query_score 보다 큰 점수들의 개수를 구하기
        #3-1.쿼리에 해당하는 score 찾음
        if query_key in info_dict:
             scoreList = info_dict[query_key] #dict에서 키워드에 해당하는 score 뽑음
             print("3.1 select result", scoreList)
             print()

             #3-2.socre보다 큰 점수들의 개수를 세는 방법 : 이분탐색
             if len(scoreList)>0:
                 start=0
                 end=len(scoreList)
                 while start< end:
                     mid=(start+end) //2
                     if scoreList[mid] >= query_score:
                         end = mid
                     else:
                         start = mid+1
                 answer.append(len(scoreList)-start)

        #3-1.쿼리에 해당하는 score가 없을때
        else:
            answer.append(0)

    return answer

 

배운점

• 새로 알게 된 내용이나 개념
• 이런상황에선 어떻게 접근해야하는지 써야하는지

---

참고 

참고한 블로그 링크