[프로그래머스] 순위 검색 (python) - 2021 KAKAO BLIND RECRUITMENT

Problem Solving

[프로그래머스] 순위 검색 (python) - 2021 KAKAO BLIND RECRUITMENT - 해시, 이분탐색

reujusong 2021. 3. 2. 19:00

1. 문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.

코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?

즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.

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

[문제]

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

2. 제한 사항

info 배열의 크기는 1 이상 50,000 이하입니다.
info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
- 개발언어는 cpp, java, python 중 하나입니다.
- 직군은 backend, frontend 중 하나입니다.
- 경력은 junior, senior 중 하나입니다.
- 소울푸드는 chicken, pizza 중 하나입니다.
- 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
query 배열의 크기는 1 이상 100,000 이하입니다.
query의 각 문자열은 "[조건] X" 형식입니다.
- [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
- 언어는 cpp, java, python, - 중 하나입니다.
- 직군은 backend, frontend, - 중 하나입니다.
- 경력은 junior, senior, - 중 하나입니다.
- 소울푸드는 chicken, pizza, - 중 하나입니다.
- '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
- X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

3. 입출력 예

info	query	result
["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"]	["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]	[1,1,1,1,2,4]

4. 나의 풀이

나는 카카오 3번에 징크스가 있다. 지금까지 치뤘던 카카오 테스트 중 유독 3번만 제대로 푼적이 한번도 없기 때문이다. 그렇기 때문에 세번의 시도 끝에 완성한 이 문제를 꼭 기록 해둬야겠다고 생각했다.

첫번째 시도

시험 당시에는 문제를 읽고 트리를 생각했다. 효율성 때문에 딕셔너리(해시)를 활용해야겠다 생각했고, 어떻게 하면 모든 경우를 고려해서 자료구조를 구성할 수 있을까 고민하다 시간도 없겠다 그냥 깊이가 4인 딕셔너리를 만들어보기로 했다. (무모 그 자체;;;;;) 매핑의 시간 복잡도가 O(4)이기 때문에 보기에는 복잡해도 탐색하기에 가장 효율적일 것이라 생각했다.

그래서 만든 딕셔너리는 다음과 같다.

    dic = {"cpp":
           {"backend":
                {"junior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "senior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "-":
                     {"pizza":[], "chicken":[], "-":[]},
                }, 
            "frontend":
                {"junior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "senior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "-":
                     {"pizza":[], "chicken":[], "-":[]},
                }, 
           "-":
                {"junior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "senior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "-":
                     {"pizza":[], "chicken":[], "-":[]},
                } 
            },


 		... 
        
        

            "frontend":
                {"junior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "senior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "-":
                     {"pizza":[], "chicken":[], "-":[]},
                }, 
           "-":
                {"junior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "senior":
                     {"pizza":[], "chicken":[], "-":[]},
                 "-":
                     {"pizza":[], "chicken":[], "-":[]},
                } 
            },
      }

괄호 열고 닫다가 눈이 빠지는줄 알았다... ㅎ

어쨌든, 저 상태에서 info 를 순회하며 정보(score)를 담아준다.

    answer = []
    for k in info:
        spl = k.split(" ")
        dic[spl[0]][spl[1]][spl[2]][spl[3]].append(int(spl[-1]))
        dic["-"][spl[1]][spl[2]][spl[3]].append(int(spl[-1]))
        dic[spl[0]]["-"][spl[2]][spl[3]].append(int(spl[-1]))
        dic[spl[0]][spl[1]]["-"][spl[3]].append(int(spl[-1]))
        dic[spl[0]][spl[1]][spl[2]]["-"].append(int(spl[-1]))
        dic["-"]["-"][spl[2]][spl[3]].append(int(spl[-1]))
        dic["-"][spl[1]]["-"][spl[3]].append(int(spl[-1]))
        dic["-"][spl[1]][spl[2]]["-"].append(int(spl[-1]))
        dic[spl[0]]["-"]["-"][spl[3]].append(int(spl[-1]))
        dic[spl[0]]["-"][spl[2]]["-"].append(int(spl[-1]))
        dic[spl[0]][spl[1]]["-"]["-"].append(int(spl[-1]))
        dic["-"]["-"]["-"][spl[3]].append(int(spl[-1]))
        dic["-"]["-"][spl[2]]["-"].append(int(spl[-1]))
        dic["-"][spl[1]]["-"]["-"].append(int(spl[-1]))
        dic[spl[0]]["-"]["-"]["-"].append(int(spl[-1]))
        dic["-"]["-"]["-"]["-"].append(int(spl[-1]))
        
    for i in query:
        ans = 0
        q, num = filterStr(i)
        for j in dic[q[0]][q[1]][q[2]][q[3]]:
            if j >= num:
                ans += 1
        answer.append(ans)
    return answer

info의 원소 하나하나는 항목을 특정하고 있지만, 쿼리를 통해 검색할 때에는 생략될 부분("-"에 해당)이 있기 때문에 2^4의 16가지 경우를 고려해줘야 한다.

이렇게 딕셔너리를 채워주고 나면, 각 key값에 해당하는 value에는 score 정보가 정렬되지 않은 상태로 저장되어 있다. 따라서 query를 순회하며 원하는 점수 이상인지 확인을 해주어야 한다.

하지만 이 단계에서 효율성이 통과하지 못하였다. 다시 올라가서 제한사항을 보면 query 배열의 크기가 1 이상 100,000 이하라고 나와있기 때문에 당연히 시간 초과가 날 수밖에 없다 .... 😇🔫

테스트 당시에는 주어진 시간이 부족하여 이 상태로 제출하였고, 프로그래머스에 문제가 올라오고 나서 다시 풀이해보았다.

두번째 시도

쿼리를 순회하며 점수를 확인하는 것이 효율적이지 않다는 것을 깨닫고 나서 info를 저장하는 과정에서 정렬을 수행하기로 했다. 그러려면 값이 저장될 때마다 오름차순 유지를 하며 위치를 찾아야 했다. 이 과정에서 upperbound 알고리즘을 활용했다. 이 알고리즘은 이분 탐색과 유사한 알고리즘으로, 정렬된 배열에서 target 값이 존재할 때 target 값을 초과하는 값들 중 첫번째 위치를 반환하는 함수이다.

def upperBoundSearch(arr, target):
    if len(arr) >= 1 and target > arr[-1]:
        return len(arr)
    left, right = 0, len(arr) - 1
    while (left < right):
        mid = (left + right) // 2
        if(arr[mid] <= target):
            left = mid + 1
        else:
            right = mid

    return right

예를 들어, [1,2,5,7,9]라는 배열에서 target을 6으로 지정하면 아웃풋으로 3을 내보낸다. 이 함수를, 딕셔너리에 값을 저장할 때 마다 수행해준다.

# 수정 전
dic[spl[0]][spl[1]][spl[2]][spl[3]].append(int(spl[-1]))

# 수정 후
idx = upperBoundSearch(dic[spl[0]][spl[1]][spl[2]][spl[3]], int(spl[-1]))
dic[spl[0]][spl[1]][spl[2]][spl[3]].insert(idx, int(spl[-1]))

이 과정을 거치면, 쿼리를 순회하며 점수를 필터링하는 과정을 줄일 수 있다. 그냥 전체 점수 갯수에서 lowerBoundSearch를 수행한 개수를 빼서 리턴하면 끝이다.

* lowerBoundSearch: 정렬된 배열에서 target 값이 존재할 때 target 값보다 크거나 같은 값들의 첫번째 위치를 반환한다.

    for i in query:
        ans = 0
        q, num = filterStr(i)
        scores = dic[q[0]][q[1]][q[2]][q[3]]
        answer.append(len(scores) - lowerboundSearch(scores, num))
    return answer

이렇게 풀어서 제출하면 효율성까지 모두 통과하지만... 전체 코드 길이가 200줄이 넘는다 ㅋㅋㅋㅋㅋ

세번째 시도

두번째 풀이로 문제를 해결하긴 했지만, 이대로 냅두다간 프로그래머스의 '다른 사람의 풀이' 탭을 통해서 내 코드를 보는 사람들이 나를 '노가다의 왕'으로 볼 것이 뻔하기 때문에 무조건 리팩토링을 해야했다.... 후

가장 먼저, 자료구조를 뜯어 고쳐야 했다. key-value 매핑이 필요하다는 생각은 변함이 없었지만 깊이가 4인 딕셔너리는 내가 봐도 에바참치였기 때문에 깊이를 1이 되도록 수정했다.

dic = {}
    
for l in ('cpp', 'java', 'python', '-'):
    for i in ('backend', 'frontend', '-'):
        for s in ('senior', 'junior', '-'):
            for f in ('pizza', 'chicken', '-'):
                dic[l+i+s+f] = []

(딕셔너리의 깊이를 줄이니 반복문이 4중이 되는 매-직)

이렇게 딕셔너리를 구성하면 key 양식은 'cppbackendjuniorchicken', '-frontend-pizza' 이런 문자열 형태가 된다.

그 다음, info 배열을 순회하며 마찬가지로 2^4 가지 경우에 대해 딕셔너리에 값을 저장한다.

def parseInfo(info):
    arr = info.split(' ')
    keys = []
    for i in (arr[0], '-'):
        for j in (arr[1], '-'):
            for k in (arr[2], '-'):
                for l in (arr[3], '-'):
                    keys.append(i+j+k+l)
    return keys, int(arr[-1])
    
def solution(info, query):

	...

    for l in info:
        keys, score = parseInfo(l)
        for key in keys:
            dic[key].append(score)

이렇게 값을 모두 저장하고 나면, 딕셔너리의 각 value들은 정렬이 되지 않은 상태로 저장되어있다. query를 순회하기 전에 이 값들을 정렬하는 과정이 필요하다.

그 이후 마지막으로, query를 순회하며 위처럼 answer 배열에 저장하면 끝이다.

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

    for i in query:
        q, num = parseQuery(i)
        scores = dic[q]
        answer.append(len(scores) - lowerboundSearch(scores, num))
    return answer

리팩토링을 완료한 최종 코드는 다음과 같다.

def lowerboundSearch(arr, target):
    if len(arr) == 0 or (len(arr) >= 1 and target > arr[-1]):
        return len(arr)
    left, right = 0, len(arr) - 1
    while (left < right):
        mid = (left + right) // 2
        if(arr[mid] < target):
            left = mid + 1
        else:
            right = mid

    return right

def parseQuery(s):
    string = s.replace("and ", "").split(" ")
    number = int(string[-1])
    return ''.join(string[:-1]), number

def parseInfo(info):
    arr = info.split(' ')
    keys = []
    for i in (arr[0], '-'):
        for j in (arr[1], '-'):
            for k in (arr[2], '-'):
                for l in (arr[3], '-'):
                    keys.append(i+j+k+l)
    return keys, int(arr[-1])

def solution(info, query):
    answer = []
    dic = {}
    
    for l in ('cpp', 'java', 'python', '-'):
        for i in ('backend', 'frontend', '-'):
            for s in ('senior', 'junior', '-'):
                for f in ('pizza', 'chicken', '-'):
                    dic[l+i+s+f] = []

    for l in info:
        keys, score = parseInfo(l)
        for key in keys:
            dic[key].append(score)
    
    for k in dic.keys():
        dic[k].sort()

    for i in query:
        q, num = parseQuery(i)
        scores = dic[q]
        answer.append(len(scores) - lowerboundSearch(scores, num))
    return answer

최종 코드도 깔끔하진 않아서 다른 솔루션을 참고하고 이후에 더 고민해봐야 겠다. 역시 효율성 딸린 문제는 너무 어렵다 🥶

문제 링크: programmers.co.kr/learn/courses/30/lessons/72412

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

["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] ["java and backend and junior and pizza 100","pyt

programmers.co.kr

전체 코드: gist.github.com/songjucho/081580456238fce106e37def85c0524c

프로그래머스 순위 검색 풀이

프로그래머스 순위 검색 풀이. GitHub Gist: instantly share code, notes, and snippets.

gist.github.com

'Problem Solving' 카테고리의 다른 글

[프로그래머스] 거리두기 확인하기 (Python) - 2021 카카오 채용연계형 인턴십 - 구현 (0)	2021.07.12
[프로그래머스] 쿼드압축 후 개수 세기(Python) - 재귀 (0)	2021.03.30
[프로그래머스] 합승 택시 요금 (python) - 2021 KAKAO BLIND RECRUITMENT - 다익스트라 (0)	2021.02.03
[프로그래머스] 메뉴 리뉴얼 (python) - 2021 KAKAO BLIND RECRUITMENT (0)	2021.01.25
[프로그래머스] 위장 - 해시 (Swift/Python) (0)	2020.08.25

현재글[프로그래머스] 순위 검색 (python) - 2021 KAKAO BLIND RECRUITMENT - 해시, 이분탐색

how sweet you are!

iOS, 앱개발, 하이브리드앱, git, 알고리즘

스택, ios, 부스트캠프, 알고리즘, 이분탐색, 카카오코테, Swift, github, 앱개발, programmers, 파이썬, 코딩테스트, 그리디, 카카오블라인드, python, 프로그래머스, 부스트코스, 기본문법, Algorithm, 탐욕법,

Today :
Yesterday :

how sweet you are!