[PRO] 2023 KAKAO BLIND RECRUITMENT 기출 풀이 (Python)

1. 개인정보 수집 유효기간

소요시간: 25분, 유형: 구현

날짜 처리를 잘 하면 풀리는 문제였다. 이때 나는 기준일을 문제에서 주어지는 제일 최소 날짜를 기준으로 며칠 지났는지로 계산했는데, 그냥 0년 0월 0일을 기준으로 계산해도 되는 것 같은데 고민을 한번 해봐야겠다.

def get_base_days(date_str: str) -> int:
    """2020.01.01 기준 며칠 지났는지 반환"""
    days = 0
    YYYY,MM,DD = map(int, date_str.split('.'))
    days += (YYYY-2000)*12*28
    days += (MM-1)*28
    days += (DD-1)
    return days
    

def solution(today, terms, privacies):
    answer = []
    today_base_days = get_base_days(today)
    
    # 약관 타입별 보유일자 저장
    term_days_dict = dict()
    for term in terms:
        term_type, term_month = term.split()
        term_days_dict[term_type] = int(term_month)*28
    
    for i,privacy in enumerate(privacies):
        from_date, term_type = privacy.split()
        
        # 파기되어야 할 첫 날짜
        destroy_base_days = get_base_days(from_date) + term_days_dict[term_type]
        if destroy_base_days <= today_base_days:
            answer.append(i+1)
            
    return answer

2. 택배 배달과 수거하기

소요시간: 40분, 유형: 그리디

문제는 복잡해보이지만 읽으면서 그리디하게 선택하는 방법을 택하게 될 것 같다고 예상했고, 문제 예시를 통해 그 규칙을 발견할 수 있었다. 같은 수를 중복해서 리스트에 저장하는 스킬을 생각해냈는데 꽤 괜찮은 것 같다.

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    # 집 번호를 중복해서 오름차순으로 쌓기
    del_houses = []
    pick_houses = []
    
    for idx, d in enumerate(deliveries):
        house_num = idx+1
        for _ in range(d):
            del_houses.append(house_num)
    
    for idx, p in enumerate(pickups):
        house_num = idx+1
        for _ in range(p):
            pick_houses.append(house_num)
    
    # 끝에서부터 지워나가기
    while del_houses or pick_houses:
        # 정답 갱신
        d_max_house = del_houses[-1] if del_houses else 0
        p_max_house = pick_houses[-1] if pick_houses else 0
        answer += max(d_max_house, p_max_house) * 2
        
        
        # 끝에서부터 cap만큼 제거
        for _ in range(cap):
            if del_houses:
                del_houses.pop()
            if pick_houses:
                pick_houses.pop()
    
    return answer

3. 이모티콘 할인 행사

소요시간: 50분, 유형: 브루트포스(완전탐색)

문제를 읽으며 모든 경우의 수를 탐색해서 구해야 할 것 같다고 생각하고 제약조건의 m ≤ 7을 보고 브루트포스 문제임을 확신했다.

이때, 수도코드를 손코딩으로 어느정도 적고 코드에 돌입한게 큰 도움이 되었다.

모든 경우의 수 구할 때 이용하는 itertools 모듈 항상 잘 정리해두자. product에서 repeat 키 값이 생각안났는데, 검색 허용이 안되는 환경이면 못 찾을거다.

이 문제에서 시간이 오래걸린건 일부 테스트 케이스가 틀려서 그 이유를 찾는 과정에서 시간이 많이 소요되었다. 문제를 다시 정독하고, 내 코드를 다시 꼼꼼히 보아도 이유를 찾을 수 없어 질문하기 탭에서 도움을 구했는데 정말 엉뚱한 곳에 이유가 있었다.

할인율을 계산할 때 나눗셈을 너무 빨리 해버려서 발생하는 문제였다. 무조건 나눗셈은 최대한 늦게 계산하도록 해야겠다고 결심했다.

추가로 할인율인데 그 자체를 곱하는 실수도 했었어서 이런 실수도 조심해야겠다..ㅎ

from itertools import product

def solution(users, emoticons):
    results = [] # [(가입자수, 매출),...] 형태로 모든 경우 담기용
    
    # 할인율 경우의 수
    discount_percents_cases = list(product([10,20,30,40],repeat=len(emoticons)))
    for discount_percents in discount_percents_cases:
        subscribe_cnt = 0 # 가입자수
        total_sales = 0 # 매출
        
        for criteria_percent, criteria_price in users:
            # 이모티콘 구매금액 구하기
            user_sales = 0
            for discount_percent, emoticon_price in zip(discount_percents, emoticons):
                if discount_percent >= criteria_percent: # 구매
                    # !할인율이니까 1에서 빼야됨
                    user_sales += (emoticon_price*(100-discount_percent))//100 # 정가 100의배수
                    
            if user_sales >= criteria_price:
                subscribe_cnt += 1
            else:
                total_sales += user_sales
        
        results.append((subscribe_cnt, total_sales))
    
    results.sort(key = lambda x: (-x[0],-x[1]))
    return results[0]

4. 표현 가능한 이진트리

소요시간: 70분, 유형: 재귀, 분할 정복, 이진트리

문제의 조건을 읽고 표현 불가능한 경우가 어떨 때인지 알아냈어야 하는 문제다. 이 부분을 빨리 파악하지 못해서 시간이 꽤 걸렸다.

또, 알아낸 조건에서 부정확한 부분이 있었는데, 가운데 값이 0이고 길이가 1이 아니면 불가능한 경우라고 처음에 생각했는데, 모두 더미노드인 0b000과 같은 경우도 가능한 경우였다. 이것도 질문하기 탭을 통해 얻은 정보라 실전이었으면 끝까지 파악 못했을 수도 있었을거다. 이런 놓치는 케이스 찾는 연습이 필요할 듯.

또, 길이가 $2^N-1$이 될 때까지 앞에 0을 채워넣는 코드를 작성하는데 오래걸렸다. 검색해서 비트연산을 통해 해결했는데, 추후 또 쓰일 때를 대비해서 기억해놔야 할 것 같다.

십진수를 이진수 문자열로 변환하는 코드도 빠르게 작성했어야 하는데 계속 더해나가고 마지막에 뒤집어야 하는걸 빼먹어서 시간이 좀 걸렸다. 원리를 생각하면서 기억하자.

시간이 오래걸려서 시간복잡도도 제대로 계산 못해고 제출했는데, 계산 다시 정확히 해봐야 할 듯.

def is_valid(tree_str):
    """표현 가능한 tree형태인지"""
    # 길이 1이면 종료 & True반환
    if len(tree_str) == 1:
        return True
    
    mid_idx = len(tree_str)//2
    # !모두 0이 아니면서 가운데가 0이면 False반환
    if tree_str[mid_idx] == "0" and len(set(tree_str))>=2:
        return False
    
    # 아니면 좌우 is_valid 재귀 호출
    if is_valid(tree_str[:mid_idx]) and is_valid(tree_str[mid_idx+1:]):
        return True
    else:
        return False

def check_possible(number):
    # 2진수 문자열로 변환
    binary_str = ""
    while number:
        number,remainder = divmod(number,2)
        binary_str += str(remainder)
    binary_str = binary_str[::-1] #!마지막에 뒤집어줘야됨
    
    # TODO !2^n-1 될때까지 앞에 0채우기
    while ((len(binary_str)+1) & (len(binary_str))):
        binary_str = "0" + binary_str    
        
    # is_valid 호출(재귀로 처리)
    return is_valid(binary_str) 


def solution(numbers):
    answer = []
    
    for number in numbers:
        if check_possible(number):
            answer.append(1)
        else:
            answer.append(0)
    
    return answer

공식 풀이

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

올해는 효율성 테스트 문제없이 7 문제가 출제되었으며, 난이도는 작년과 비슷했습니다. 문제는 쉬운 난이도부터 어려운 난이도 순으로 배치되었고, 올해 문제의 특징은 특별한 알고리즘을 사용하지 않아도 풀 수 있다는 점입니다.