[카카오] 2021 블라인드 공채 - 순위 검색

작성일 | In |

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

작년 9월에 신입공채 1차 코딩테스트가 있었습니다. 그 중 효율성을 통과하지 못했던 문제인데, 프로그래머스에 문제가 올라와 풀이합니다.

가장 큰 문제는 Graph 구조로 이 문제에 접근했다는 점입니다. Trie를 이용해 모든 경우의 수를 이어서 탐색하는 방식으로 접근했는데, 정확성은 통과했지만 효율성을 통과하지 못했습니다.

이 문제는 한 번에 원하는 조건의 지원자 수에 접근할 수 있도록 풀어야 시간 초과가 나지 않습니다.

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

해설은 이 곳에 나와있습니다.

코드

get_subset

1
2
3
4
5
6
7
8
9
10
11
12
13
def get_subset(arr): # info에서 -를 포함해 가능한 모든 경우의 수를 부분집합으로 구함.
    n = len(arr)
    result = []
    for i in range(1 << n):
        temp = []
        for j in range(n):
            if i & (1 << j):
                temp.append(j)
        temp_arr = arr[:]
        for idx in temp:
            temp_arr[idx] = '-'
        result.append(' '.join(temp_arr))
    return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def get_answer_by_binary_search(score, arr):
    if not arr: return 0
    start, end = 0, len(arr)
    mid = (start + end) // 2

    while start < end: # 기준 점수 이상이 처음 나오는 위치를 찾음.
        mid = (start + end) // 2
        value = arr[mid]
        if value >= score:
            end = mid
        else:
            start = mid+1

    return len(arr) - end

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(info, query):
    answer = []
    answer_dict = {}
    for i in info:
        i = i.split(' ')
        for res in get_subset(i[:-1]):
            answer_dict[res] = answer_dict.get(res, [])
            answer_dict[res].append(int(i[-1]))

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

    for q in query:
        q_list = q.split(' ')
        score = int(q_list.pop())
        q_list = [word for idx, word in enumerate(q_list) if idx%2 == 0]
        condition = ' '.join(q_list)
        answer.append(get_answer_by_binary_search(score, answer_dict.get(condition)))

    return answer

solution에서 하는 일은 간단합니다.

"java backend junior pizza 150" 형태로 들어오는 info에서 “java backend junior pizza”만을 분리한 뒤, 이 info가 속할 수 있는 모든 경우의 수를 구합니다. get_subset 함수가 이 역할을 하게 됩니다.

언어 직군 경력 소울 푸드 점수
java backend junior pizza 150
– backend junior pizza 150
java – junior pizza 150
java backend – pizza 150
java backend junior – 150
– – junior pizza 150
– backend – pizza 150
… (생략)        
java – – – 150
– – – – 150 
1
2
3
4
5
# get_subset을 통해 얻게 되는 list는 다음과 같습니다.

# ["java backend junoir pizza", "- backend junoir pizza", "java - junior pizza", "java backend - pizza", "- - junior pizza", ......]

# 위 list의 원소가 딕셔너리의 key가 되고, value인 list에 점수를 append합니다.

lower bound(binary search)를 이용해 답을 구하기 때문에 모든 value를 정렬해주고, 답을 구합니다. get_answer_by_binary_search 함수가 이 역할을 하게 됩니다.


검색 조건을 어떻게 그룹화하느냐에 따라 효율성 체크 여부가 갈렸던 문제입니다. 보자마자 Trie가 생각나서 다른 방법은 미처 생각하지 못했는데 조금 더 유연한 사고로 코딩테스트에 임해야겠습니다.