코딩 테스트 풀이 - 2021 카카오 블라인드 1차 (1~4번 문제)

문제 해설 공식 사이트

---

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

 

1번 문제

---

핵심 키워드 : 문자열 조작 + 구현

총 7가지의 단계를 단순 구현해내면 풀리는 문제다.

1단계 : str.lower() 를 통해 소문자로 변경

2단계 : string.digit(0~9) strings.ascii_lowercase(a~z) 를 알고 있으면 더 수월했을 것임.

3단계 : (주의) ..이 없어질 때 까지 ..을 .으로 변환해야함.

4단계 : 빈문자인지 check해주고 문자열 슬라이싱

5단계 : 빈문자이면 a 대입

6단계 : 길이가 16이상이면 문자열 슬라이싱으로 앞에서 15개 뽑고, 끝자리 .아닐때 까지 제거

7단계 : 길이 확인해서 부족한 만큼 늘려주기

 

코딩테스트 연습 - 신규 아이디 추천

import sys,string
def solution(new_id):
    answer = ''
    
    # 1단계
    new_id = new_id.lower()
        
    # 2단계
    arr = '0123456789-_.'
    new_new_id = []
    for s in new_id:
        if s in arr or s in string.ascii_lowercase:
            new_new_id.append(s)
            
    new_id = ''.join(new_new_id)
    
    # 3단계
    while '..' in new_id:
        new_id = new_id.replace('..','.')
        
    # 4단계
    if new_id and new_id[0] == '.':
        new_id = new_id[1:]
    if new_id and new_id[-1] == '.':
        new_id = new_id[:-1]
    
    # 5단계
    if not new_id:
        new_id = "a"
        
    # 6단계
    if len(new_id) >= 16:
        new_id = new_id[:15]
        while new_id[-1] == '.':
            new_id = new_id[:-1]
            
    # 7단계
    if new_id:
        last_str = new_id[-1]
        size = 3-len(new_id)
        if size <= 2:
            new_id = new_id + last_str * size
            
    answer = new_id
    return answer

 

 

2번 문제

---

핵심 키워드 : 조합

전체 주문들을 반복하며 course 메뉴 개수만큼 조합(combination) 한 뒤, 가장많이 주문된 조합을 찾는 문제다. 

1번 주문이 A,B,C 이고 course 메뉴 개수가 2면 (A,B), (B,C), (A,C) 3가지 가능.

여기서 2번 주문이 AC, 3번 주문이 BC인 경우에 answer 배열에 AC, BC 둘 다 들어가야 함.

 

 

코딩테스트 연습 - 메뉴 리뉴얼

import itertools

def solution(orders, course):
    answer = [] 
    orders = list(map(set, orders))
    order_combinations = []
    menu_dict = dict()
    for cnt in course: 
        menu_dict[cnt] = []

    for menu in orders:
        size = len(menu)
        for cnt in course:
            if cnt < size:
                items = list(map(''.join, list(itertools.combinations(sorted(menu),cnt))))
                order_combinations += items
            elif cnt == size:
                order_combinations.append(''.join(sorted(menu)))

    for item in set(order_combinations):
        cnt = order_combinations.count(item)
        if cnt >=2 :
            menu_dict[len(item)].append((cnt,item))
    # 각 요소들의 개수를 count 하여 가장 많이 등장한 것 확인

    for i, c in list(menu_dict.items()):
        max_cnt = 0
        arr = []
        for cnt, menu in c:
            if max_cnt < cnt:
                max_cnt = cnt
                arr = [menu]
            elif max_cnt == cnt:
                arr.append(menu)
        answer+=arr

    answer.sort()  
    return answer

(잡담)

처음부터 모든 주문에 대한 조합을 바로 구하면 무조건 시간초과 날 것이라 생각해서 어떻게든 전처리를 하고 조합을 구해야된다 생각했다.. 처음에 문제를 대충 읽고 집합 문제로 착각해서 set()로 변환시킨 뒤 각 주문들의 합집합(intersection)을 구했다. 그 결과에 조합(combination)을 구했는데 답이 안나오는거다. 어떻게 해야할 지 한참 고민하다가, 처음부터 조합을 바로 구해봤는데 너무나 쉽게 정답이 나와서 어이가 없었다.
아무래도 효율성 안따지는 문제는 복잡한 생각없이 푸는게 좋아 보인다.

 

3번 문제

---

핵심 키워드 : 전처리 + 이분탐색

입력 데이터 전처리를 얼마나 효율적으로 해내는가에 모든것이 달려있는 문제이다.

전처리 방법은 아래와 같이 만들 수 있는 모든 경우를 다 만들어 버리는 것이다.

java backend junior pizza 150 
- backend junior pizza 150 
java - junior pizza 150 
java backend - pizza 150 
java backend junior - 150 
- - junior pizza 150
...
- - - - 150

그리고 저것을 문자로 변환(''.join()) 해서 딕셔너리 키로쓰고, 값으로는 점수가 들어간다.

이렇게 하는 이유는 X점수 이상이라는 쿼리를 날릴때 이분탐색을 써서 시간을 줄이기 위함이다.

전처리만 잘해두었으면 쿼리는 단 몇 줄로 끝나버린다. wow
만약 전처리를 안했다면 극단적인 케이스에서 시간초과를 버틸 수 없을 것이다.

 

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

import bisect, itertools
def solution(info, query):
    answer = []
    for index, value in enumerate(info):
        info[index] = list(value.split())
        info[index][-1] = int(info[index][-1])

    info.sort(key=lambda x : x[4])
    arr = [0,1,2,3]

    # new_info["문자열값"] = [오름차순 점수]
    # 사전에 모든 조합을 만들어버림
    new_info = dict()
    for person_info in info:
        combi_arr = set()
        combi_arr.add(''.join(person_info[:-1]))
        score = person_info[-1]
        for i in range(1,5):
            for it in list(itertools.combinations(arr,i)):
                tmp_info = person_info[:-1]
                for idx in it:
                    tmp_info[idx] = '-'
                key = ''.join(tmp_info)
                combi_arr.add(key)
        for key in combi_arr:
            if key not in new_info:
                new_info[key] = [score]
            else : 
                new_info[key].append(score)

    # 쿼리 시작
    for index, value in enumerate(query):
        new_query = value.split(' and ')
        new_query[-1], score  = new_query[-1].split()
        new_query = ''.join(new_query)
        score = int(score)
        size = 0
        # 점수 X 이상인 것
        if new_query in new_info:
            size = len(new_info[new_query]) - bisect.bisect_left(new_info[new_query], score)
        answer.append(size)
    return answer

(잡담)

앞으로 이런 고정된 데이터에 여러 번의 쿼리가 나오는 문제는 무조건 전처리에 힘을 다 쏟아부어야겠다고 다짐하게 만든 문제였다...

 

4번 문제

---

핵심 키워드 : 최단 경로 탐색 (플로이드 워셜 / 다익스트라)

S에서 시작해서 A,B가 각각 집으로 가는 문제다

1) S에서 A,B가 같이 택시타고 가다가 도중에 내려서 각자의 길을 가거나,
2) 처음부터 A,B가 따로 각자의 길을 갈 수 있다.

 

정점 개수가 200개 이하라는 것만 보고도, 이미 알 사람들은 플로이드 워셜이라는 것을 알았을 것이다.

※ C++은 O(n^3)이 500개 까지 버티지만 python은 200개 까지 버티므로 200개로 출제한 것으로 추측됨.

 

단순히 플로이드 워셜이라 알고리즘을 알고 있었고, 문제 풀어본 경험만 있어도 앞의 2,3번 문제보다 더 수월하게 해결된다.

정답은 최단경로 배열 arr[s→k] + arr[k→a] + arr[k→b] 중에서 가장 작은 값이다.

 

코딩테스트 연습 - 합승 택시 요금

import sys
def solution(n, s, a, b, fares):
    INF = n*100000+1
    matrix = [[INF for j in range(n)] for i in range(n)]
    for i in range(n):
        matrix[i][i] = 0

    for c,d,cost in fares:
        matrix[c-1][d-1] = cost
        matrix[d-1][c-1] = cost

    for k in range(n):
        for i in range(n):
            for j in range(n):
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

    return min(matrix[s-1][k] + matrix[k][a-1] + matrix[k][b-1] for k in range(n))