카카오_2021_순위 검색_딕셔너리_해시테이블_replace(a,b)

난이도가 좀 있다 - 3번문제

• 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72412?language=python3

---

솔루션 코드 - 내가 푼

• 정확도만 다 맞고 효율성은 다 틀림(40점)

''' 정답 - 정확성은 다 맞고 효율성은 다 틀린 ver '''
def preprocessing(infos, queries):
    info = []
    query = []
    
    # 전처리  -> 다음부턴 query.replace(" and ", "") 를 사용하도록 하자..
    for i in infos:
        info.append(i.split(' '))   # 단어단위로 우선 저장
        
    for i in queries:
        query.append(i.split(' and '))  
        
    for i in query:     
        tmp1, tmp2 = i.pop().split(' ')
        i.append(tmp1)
        i.append(tmp2)
    
    return info, query

def solution(infos, queries):
    answer = []
    ans = 0
    minus_num = 0
    
    info, query = preprocessing(infos, queries)
    
    for sql in query:
        for data in info:            
            # '-'를 고려한 경우(+ 점수가 더 높은 것 중)
            if '-' in sql and int(sql[-1]) <= int(data[-1]):
                for i in range(4):                                       # 마지막 점수 제외
                    if sql[i] != '-' and sql[i] == data[i]:
                        minus_num += 1
                        
                if (4 - minus_num) == sql.count('-'):
                    ans += 1
                minus_num = 0                        
                
            # '-'를 고려하지 않은 경우
            elif int(sql[-1]) <= int(data[-1]) and sql[:4] == data[:4]:
                ans += 1        
        
        answer.append(ans)                                                # 각 조건에 맞는 걸 하나씩 체크한 결과를 여기에 이제 최종 answer.append(숫자)
        ans = 0
        
    return answer

info = ["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"]
query = ["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"]
print(solution(info, query))

---

솔루션 코드 - 다른 사람이 푼

• 단순히 봐도 info 50,000개 x query 100,000개 = 50억개. 하나씩 비교해선 답이 없습니다. 해시테이블을 사용합시다.
  • 해시테이블??? = 딕셔너리???

def solution(infos, queries):
    answer = []

    # 총 경우의 수 (108가지)
    info_dict = {}

    for lang in ['cpp', 'java', 'python', "-"]:
        for job in ['backend', 'frontend', "-"]:
            for career in ['junior', 'senior', "-"]:
                for food in ['chicken', 'pizza', "-"]:
                    info_dict[lang + job + career + food] = []
    
    # 지원자의 경우의 수 (1인, 16가지)
    for info in infos:
        info = info.split(" ")
        for lang in [info[0], "-"]:
            for job in [info[1], "-"]:
                for career in [info[2], "-"]:
                    for food in [info[3], "-"]:
                        info_dict[lang + job + career + food].append(int(info[4]))

    # 시간초과를 해결한 방법
    for key in info_dict.keys():
        info_dict[key].sort()

    # 조건
    for query in queries:
        query = query.replace(" and ", "")
        query = query.split()

        query_score = int(query[1])
        query = query[0]

        # 점수
        info_score = sorted(info_dict[query])  # 시간초과가 나는 이유
        l = len(info_score)
        tmp = l

        low, high = 0, l - 1

        while low <= high:
            mid = (low + high) // 2

            if query_score <= info_score[mid]:
                tmp = mid
                high = mid - 1

            else:
                low = mid + 1

        answer.append(l - tmp)
    return answer


print(solution(["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"]))

---

카카오 공식 해설 링크

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