프로그래머스 Lv2 순위 검색 Python

문제 링크

2021 KAKAO BLIND RECRUITMENT

코딩테스트 연습 | 프로그래머스 스쿨

정답 코드

dictLanguage = {
    "cpp": "1",
    "java": "2",
    "python": "3",
    "-": "4",
}
dictOccupation = {
    "backend": "1",
    "frontend": "2",
    "-": "3"
}
dictCareer = {
    "junior": "1",
    "senior": "2",
    "-": "3"
}
dictSoulFood = {
    "chicken": "1",
    "pizza": "2",
    "-": "3",
}

dictInfo = dict()

def solution(info, query):
    lenQuery = len(query)
    answer = [0 for _ in range(lenQuery)]
    for i in info:
        i = i.split()
        stack = ["" for _ in range(5)]
        stack[0] = dictLanguage[i[0]]
        stack[1] = dictOccupation[i[1]]
        stack[2] = dictCareer[i[2]]
        stack[3] = dictSoulFood[i[3]]
        stack[4] = int(i[4])
        for a in (stack[0], "4"):
            newStringA = a
            for b in (stack[1], "3"):
                newStringB = newStringA + b
                for c in (stack[2], "3"):
                    newStringC = newStringB + c
                    for d in (stack[3], "3"):
                        newStringD = newStringC + d
                        if dictInfo.get(newStringD):
                            dictInfo[newStringD].append(stack[4])
                        else:
                            dictInfo[newStringD] = [stack[4]]

    for key in dictInfo:
        dictInfo[key].sort()
                                                  
    for idx in range(lenQuery):
        q = query[idx].split(" and ")
        tmp = q[3].split()
        newString = dictLanguage[q[0]] + dictOccupation[q[1]] + dictCareer[q[2]] + dictSoulFood[tmp[0]]
        
        scoreQ = int(tmp[1])
        if dictInfo.get(newString):
            tmpList = dictInfo[newString]
            lenTmpList = len(tmpList)
            start, end = 0, lenTmpList
            while start < end:
                mid = (start + end) // 2
                if tmpList[mid] < scoreQ:
                    start = mid + 1
                else:
                    end = mid
            answer[idx] = lenTmpList - start
    return answer

리팩토링

dictLanguage = {
    "cpp": 1,
    "java": 2,
    "python": 3,
    "-": 4
}
dictOccupation = {
    "backend": 10,
    "frontend": 20,
    "-": 30
}
dictCareer = {
    "junior": 100,
    "senior": 200,
    "-": 300
}
dictSoulFood = {
    "chicken": 1000,
    "pizza": 2000,
    "-": 3000,
}

dictInfo = dict()

def solution(info, query):
    lenQuery = len(query)
    answer = [0 for _ in range(lenQuery)]
    for i in info:
        i = i.split()
        stack = [0 for _ in range(5)]
        stack[0] = dictLanguage[i[0]]
        stack[1] = dictOccupation[i[1]]
        stack[2] = dictCareer[i[2]]
        stack[3] = dictSoulFood[i[3]]
        stack[4] = int(i[4])
        for a in (stack[0], 4):
            newNumberA = a
            for b in (stack[1], 30):
                newNumberB = newNumberA + b
                for c in (stack[2], 300):
                    newNumberC = newNumberB + c
                    for d in (stack[3], 3000):
                        newNumberD = newNumberC + d
                        if dictInfo.get(newNumberD):
                            dictInfo[newNumberD].append(stack[4])
                        else:
                            dictInfo[newNumberD] = [stack[4]]

    for key in dictInfo:
        dictInfo[key].sort()
                                                  
    for idx in range(lenQuery):
        q = query[idx].split(" and ")
        tmp = q[3].split()
        newNumber = dictLanguage[q[0]] + dictOccupation[q[1]] + dictCareer[q[2]] + dictSoulFood[tmp[0]]
        
        scoreQ = int(tmp[1])
        cnt = 0
        if dictInfo.get(newNumber):
            tmpList = dictInfo[newNumber]
            lenTmpList = len(tmpList)
            start, end = 0, lenTmpList
            while start < end:
                mid = (start + end) // 2
                if tmpList[mid] < scoreQ:
                    start = mid + 1
                else:
                    end = mid
            answer[idx] = lenTmpList - start
    return answer

실행 결과

- string key를 넣은 dictionary

- number key를 넣은 dictionary

풀이 방법

- 우선 직접 비교를 하게 될 경우 연산 횟수를 간략하게 계산해본다.

    - info 가 50,000개 query가 100,000개 이고 5개씩 잘라서 계산 할 경우

        - 5 * 5 * 5 * 10 ** 9 = 5e3 * 10e9

        - 무조건 시간초과

- 다른 것은 필요 없고 점수만을 가지고 비교하게 만들어야 한다.

    - 딕셔너리를 통해서 암호 코드를 만든다.

    - "-"도 포함해서 만들어줘야 한다.

        - 왜냐하면 query에 있는 원소를 잘라서 만들 때 "-"가 존재하는데 모든 경우를 포함하기 때문이다.

        - cpp and - and - and - 150 인 경우를 예로 든다.

            - info의 원소가 cpp frontend junior pizza 200인 경우 그냥 단순하게 2111이라는 암호코드를 사용하면 조건에 해당하지 않은 것처럼 된다.

           - 따라서 2111을 가지고 2311도 만들어보고 2131도 만들어보는 등 총 16가지의 조합을 가지고 dictInfo에 넣어준다.

- 16가지의 암호 조합 마다 점수를 int값으로 변환해서 append해준다.

- 이진탐색을 실시한다.

    - dictInfo를 query를 돌기 직전에 미리 정렬시킨다.

        - query를 돌면서 그 때마다 정렬을 시키면 100,000 * 정렬할 list의 길이

        - 뭐 말 안해도 알 것이다. 시간초과 ㅅㄱ

    - 이진탐색의 시간 복잡도는 O(logN)
    - 찾은 인덱스 번호를 통해서 조건의 점수보다 높은 원소의 개수를 파악할 수 있다.

        - lenTmpList - start

        - 이걸 미리 만들어놓은 answer[idx]에 넣어주면 끝

 

느낀점

1. 이게 level2라고? 거짓말 치지마;;

2. 반복문은 2번 돌리는 것은 멍청한 짓이다.

3. 딕셔너리를 적극적으로 활용하자

4. 값을 찾을 때는 무조건 이진탐색

5. 정렬을 시키고 반복문을 돌릴것 => 반복문을 돌리면서 새로운 정렬을 시도하지 말것

6. 조합, 순열 등 itertools를 적극 활용할것

7. 모르면 하드코딩