Q3. 순위 검색

Programmers를 통해 공개되어 있는 문제를 통해 알고리즘 역량을 향상시키고자 작성하고 있습니다.
알고리즘의 허점이나 더 간결한 아이디어가 있다면 언제든 지적해주세요.

1. 문제 유형

문제 설명

문제 및 입출력 예시

문제에 대한 더 상세한 설명은 Programmer를 참고해주시기 바랍니다.
https://programmers.co.kr/learn/courses/30/lessons/72412

2. 소스 코드

Python으로 작성한 전체 코드는 다음과 같습니다.

from bisect import bisect_left
from itertools import combinations

def makeCase(info):
    cases = []
    
    for idx in range(5):
        for combi in combinations([0,1,2,3],idx):
            tmp = ''
            for n in range(4):
                if n in combi:
                    tmp += info[n]
                else:
                    tmp += '-'
            cases.append(tmp)
    return cases


def solution(info, query):
    answer = []
    dic = dict()
    
    for i in info:
        splitInfo = i.split()
        combi = makeCase(splitInfo)
        
        for cb in combi:
            if cb in dic:
                dic[cb].append(int(splitInfo[4]))
            else:
                dic[cb] = [int(splitInfo[4])]
    
    for key in dic.keys():
        dic[key].sort()
    
    for q in query:
        splitQuery = q.split()
        target = splitQuery[0]+splitQuery[2]+splitQuery[4]+splitQuery[6]
        value = int(splitQuery[7])
        
        if target in dic:
            ans = len(dic[target])-bisect_left(dic[target],value,lo=0,hi=len(dic[target]))
            answer.append(ans)
        else:
            answer.append(0)
    return answer

3. 문제 풀이

다양하고 간결한 로직이 있겠지만 본인은 모든 조합을 발견하고 이로부터 결과를 도출하는 방법을 통해 문제를 해결했다.

핵심 라이브러리

from itertools import combinations
from bisect import bisect_left

• combinations: 조합을 찾아내고 모든 쌍을 Dictionary형태로 반환하는 라이브러리 함수
• bisect_left: 이진 분할 알고리즘을 통해 정렬된 순서를 유지하도록 list에 x를 삽입할 index를 반환하는 라이브러리 함수

위의 두 라이브러리 함수가 이 문제를 해결하기 위한 주요 Key라고 볼 수 있다.

주요 로직

3-1 makeCase 함수

def makeCase(info):
    cases = []
    
    for idx in range(5):
        for combi in combinations([0,1,2,3],idx):
            tmp = ''
            for n in range(4):
                if n in combi:
                    tmp += info[n]
                else:
                    tmp += '-'
            cases.append(tmp)
    return cases

함수명은 마음대로 지었지만 함수의 역할은 param으로 주어진 list를 바탕으로 모든 조합을 만들어 반환하는 역할을 한다.

• 첫번째 for문: 몇 개의 요소(=idx)로 조합을 만들건지 지정한다. 이 문제에선 점수를 제외하고 4개의 요소가 있으므로 (0~4)가 범위라 볼 수 있다.

• 두번째 for문: combinations 함수를 통해 조합을 만든다. [0,1,2,3]에서 idx개로 만든 조합을 반환한다.
  ex) idx == 0: 조합 없음 -> combi == ''
  ex) idx == 4: 모두 사용하는 경우 -> tmp == '(0,1,2,3)'

• 세번째 for문: 현재 값(=n)이 combinations를 통해 만들어진 조합 중, 포함되면 tmp변수에 그 인덱스(=n)에 해당하는 info[n]을 추가해준다.
  만약, 포함되지 않을 경우, tmp에 '-'을 추가해준다.

복잡해보이지만 결과적으로 보면 주어진 info에 대한 모든 조합을 찾는 과정이라 할 수 있다.

3-2 메인 함수

def solution(info, query):
    answer = []
    dic = dict()
    
    for i in info:
        splitInfo = i.split()
        combi = makeCase(splitInfo)
        
        for cb in combi:
            if cb in dic:
                dic[cb].append(int(splitInfo[4]))
            else:
                dic[cb] = [int(splitInfo[4])]
    
    for key in dic.keys():
        dic[key].sort()
    
    for q in query:
        splitQuery = q.split()
        target = splitQuery[0]+splitQuery[2]+splitQuery[4]+splitQuery[6]
        value = int(splitQuery[7])
        
        if target in dic:
            ans = len(dic[target])-bisect_left(dic[target],value,lo=0,hi=len(dic[target]))
            answer.append(ans)
        else:
            answer.append(0)
    return answer

1. dictionary에 저장하기

    dic = dict()
    
    for i in info:
        splitInfo = i.split()
        combi = makeCase(splitInfo)
        
        for cb in combi:
            if cb in dic:
                dic[cb].append(int(splitInfo[4]))
            else:
                dic[cb] = [int(splitInfo[4])]

3-1에서 makeCase(info)를 통해 받아온 조합을 바탕으로 dictionary에 저장하는 작업을 진행한다.

이 때, int형으로 형변환을 강제하여 list 안에 넣어주며 이유는 밑에서 설명하겠다.

2. dictionary에 저장된 value에 대해 오름차순 sort

for key in dic.keys():
	dic[key].sort()

key에 대한 value(=list)에 대해 sorting 작업을 진행한다. 정수형으로 넣었기 때문에 숫자의 대소관계에 따라 오름차순으로 sorting되는 것을 볼 수 있다.

3. [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?

    for q in query:
        splitQuery = q.split()
        target = splitQuery[0]+splitQuery[2]+splitQuery[4]+splitQuery[6]
        value = int(splitQuery[7])
        
        if target in dic:
            ans = len(dic[target])-bisect_left(dic[target],value,lo=0,hi=len(dic[target]))
            answer.append(ans)
        else:
            answer.append(0)

위에서 언급했던 것처럼 bisect_left함수는 sorted list에서 x라는 값이 있을 때, 이 값이 들어가야 할 index를 반환한다.
이것이 바로 문제 해결의 키워드라고 볼 수 있다.

예시
ex) 각 학생이 10,20,30,40,50점을 받았을 때, 35점 이상 받은 학생 수를 구한다면 40,50점을 받은 2명이다.
index기준으로 본다면 35점이 들어가야할 자리는 3을 가리킬 것이다.

• 총 학생 수(5) - 35가 들어가야할 자리(3) = 35점 이상 받은 학생 수(2)
• len(students) - bisect_left(student,35,~,~) = 2

원리는 위와 같다고 볼 수 있다.
그러므로 이를 본 문제에 대입하게 된다면 X점 이상 받은 학생 수를 구할 수 있는 것이다.

더 알기 쉽게 설명하기엔 글재주가 부족하기 때문에 어려울거 같다...ㅜ

4. 실행 결과

위와 같은 원리로 작성 후, 결과를 돌리게 되면 다음과 같이 통과하는 것을 볼 수 있다.

5. 마무리

오늘은 combinations와 bisect_left를 활용해 문제를 풀어보았다.
확실히 Python은 알고리즘을 풀기에 사람에게 친절한 언어인 것 같다. 다양한 라이브러리를 통해 간편함을 제공하는 만큼 많이 숙지하고 있다면 이보다 좋은 언어는 없을 것 같다는 생각이 든다.
초심을 잃지말고 계속해서 전진해나가자!!

전체소스 git 링크
https://github.com/cho876/Algorithm/blob/master/Problem/Kakao/2021_kakao_blind_recruitment_q3.py