Coding 공부

from itertools import combinations

def solution(info, query):
    answer = []
    languages = ['cpp','java','python','-']
    positions = ['backend','frontend','-']
    careers = ['junior','senior','-']
    soulfoods = ['chicken','pizza','-']
    total_dict = {language : {position : {career : {soulfood : [0]*100001 for soulfood in soulfoods} for career in careers}  for position in positions} for language in languages}
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        info_list = [language,position,career,soulfood]
        for i in range(1<<4):
            temp = []
            for j in range(4):
                if i&(1<<j):
                    temp.append(info_list[j])
                else:
                    temp.append('-')
            total_dict[temp[0]][temp[1]][temp[2]][temp[3]][score] += 1
    for language in total_dict.keys():
        for position in total_dict[language].keys():
            for career in total_dict[language][position].keys():
                for soulfood in total_dict[language][position][career].keys():
                    for score in range(1,100001):
                        total_dict[language][position][career][soulfood][score] += total_dict[language][position][career][soulfood][score-1]
    for query_string in query:
        language,position,career,last_query = map(str.strip,query_string.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        answer.append(total_dict[language][position][career][soulfood][100000] - total_dict[language][position][career][soulfood][score-1])
    return answer

처음 풀었던 방식이다. dictionary를 이용해서, 각 쿼리에 맞게 저장을 하는 방식이다. 각 쿼리를 저장할때 나올수 있는 겨우의 수는 16가지이다. 그걸 만들기 위해서 조합을 만드는 방식으로 중간에 비트마스크를 활용해서 각조합을 만들고, 저장을 해주었다.

그리고 각 score에 대해서 그 이상값을 추출하면 시간이 오래걸리므로, prefix_sum을 통해 저장을 해놓은 뒤, query가 들어왔을때, 최대값이 10만에서 찾고자 하는 값-1을 빼줘서 찾아줬다.

해당 코드의 효율성 통과 시간이다.

def solution(info, query):
    answer = []
    index_dict = {'-':0,
    'cpp': 1,
    'java':2,
    'python': 3,
    'backend':1,
    'frontend' :2,
    'junior':1,
    'senior':2,
    'chicken':1,
    'pizza':2,
    }
    store_query = [[0]*100001 for _ in range(108)]
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        for ind1 in [0,index_dict[language]]:
            for ind2 in [0,index_dict[position]]:
                for ind3 in [0,index_dict[career]]:
                    for ind4 in [0,index_dict[soulfood]]:
                        ind = ind1*27 + ind2*9 + ind3*3 + ind4
                        store_query[ind][score] += 1
    for ind in range(108):
        for score in range(1,100001):
            store_query[ind][score] += store_query[ind][score-1]

    for qu in query:
        language,position,career,last_query = map(str.strip,qu.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        ind = index_dict[language]*27 + index_dict[position]*9 + index_dict[career]*3 + index_dict[soulfood]
        answer.append(store_query[ind][100000] - store_query[ind][score-1])
    

    return answer

두번째 코드는 www.youtube.com/watch?v=FX9n1PFv2K4 의 코드에서 차용해와서 푼 방식이다.

dicationry로 키를 만드니 너무 난잡해 보여서 2차원 배열로 만든 방식이다.

이 방식으로 했을때 시간이 좀 더 빨랐다.

import bisect

def solution(info, query):
    answer = []
    index_dict = {'-':0,
    'cpp': 1,
    'java':2,
    'python': 3,
    'backend':1,
    'frontend' :2,
    'junior':1,
    'senior':2,
    'chicken':1,
    'pizza':2,
    }
    store_query = [[] for _ in range(108)]
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        for ind1 in [0,index_dict[language]]:
            for ind2 in [0,index_dict[position]]:
                for ind3 in [0,index_dict[career]]:
                    for ind4 in [0,index_dict[soulfood]]:
                        ind = ind1*27 + ind2*9 + ind3*3 + ind4
                        store_query[ind].append(score)
    for ind in range(108):
        store_query[ind].sort()
    for qu in query:
        language,position,career,last_query = map(str.strip,qu.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        ind = index_dict[language]*27 + index_dict[position]*9 + index_dict[career]*3 + index_dict[soulfood]
        cnt = len(store_query[ind]) - bisect.bisect_left(store_query[ind],score)
        answer.append(cnt)
    

    return answer

마지막은 구간합으로 하면  16*100000번의 계산이 필요하므로 실행시간이 오래걸린다. 그래서 해결한 방법중 하나가 bisect라는 라이브러리를 활용한것이다.

bisect에 있는 기능 중 bisect_left는 정렬된 리스트에서, 순서대로 정렬되는 것을 유지하고, 현재값이 들어갈수 있는 위치의 왼쪽좌표를 알려준다. 즉, 자기보다 작은 값의 위치를 알려주는 것이다. 이걸 이용해서 그 리스트의 길이에서 해당 index의 위치를 빼주면 이상을 구할 수 있게된다.

이걸로 했을때가 시간이 제일 빨랐다. bisect를 이용하지 않고, 이분탐색을 직접구현해도 된다.

해당 문제는 query로 나올수 있는 경우의 수를 모두 예상하고 저장해놓는게 힘들었다.

def changeSeconds(times):
    return  sum(int(x) * 60 ** i for i, x in enumerate(reversed(times.split(':'))))
def changeString(times):
    hour = times//3600
    minute = (times-hour*3600)//60
    seconds = times%60
    return "%02d:%02d:%02d"%(hour,minute,seconds)

def solution(play_time, adv_time, logs):
    answer = ''
    play_time =  changeSeconds(play_time)
    adv_time = changeSeconds(adv_time)
    time_laps = [0]*(play_time+1)
    for timeString in logs:
        start_time,end_time = map(changeSeconds, timeString.split('-'))
        time_laps[start_time] += 1
        time_laps[end_time] -= 1

    for ind in range(1,play_time+1):
        time_laps[ind] += time_laps[ind-1]
    max_times = sum(time_laps[:adv_time])
    max_start_time = 0
    current_sum_times = max_times
    for ind in range(1,play_time+1-adv_time):
        current_sum_times = current_sum_times - time_laps[ind-1] + time_laps[ind+adv_time-1]
        if current_sum_times > max_times:
            max_times = current_sum_times
            max_start_time = ind
    answer = changeString(max_start_time)
    return answer

구간합을 이용해 푼 방식이다.

각 start와 end_time에 각각 +1, -1을 해주고,

누적값을 해준다. 그리고 그 광고시간의 길이만큼의 sum을 해주면, 해당 시간동안 보는 광고사용자의 수가 될수 있다.

def changeSeconds(times):
    return  sum(int(x) * 60 ** i for i, x in enumerate(reversed(times.split(':'))))
def changeString(times):
    hour = times//3600
    minute = (times-hour*3600)//60
    seconds = times%60
    return "%02d:%02d:%02d"%(hour,minute,seconds)

def solution(play_time, adv_time, logs):
    answer = ''
    play_time =  changeSeconds(play_time)
    adv_time = changeSeconds(adv_time)
    time_laps = [0]*(play_time+1)
    diff = [0]*(play_time+1)
    for timeString in logs:
        start_time,end_time = map(changeSeconds, timeString.split('-'))
        diff[start_time] += 1
        diff[end_time] -= 1
    diff_count = 0
    for ind in range(1,play_time+1):
        time_laps[ind] += time_laps[ind-1] + diff_count
        diff_count += diff[ind]

    max_times = time_laps[adv_time]
    max_start_time = 0
    for ind in range(1,play_time+1-adv_time):
        if time_laps[adv_time+ind] - time_laps[ind] > max_times:
            max_times = time_laps[adv_time+ind] - time_laps[ind]
            max_start_time = ind
    answer = changeString(max_start_time)
    return answer

같은 원리이지만, sum 하는 방식을 개선을 한것이다. diff_count를 해줘서 해당구간에서 보는 인원을 누적해줘서 하는 방식이다.

import heapq


def solution(n, s, a, b, fares):
    answer = float('inf')
    total_node = set(range(1,n+1))
    graph = [{} for i in range(n+1)]
    for start,end,fee in fares:
        graph[start][end] = fee
        graph[end][start] = fee
    def distra(start,end):
        nonlocal graph,n
        node_list = []
        heapq.heappush(node_list,(0,start))
        INF = float('inf')
        Fee_list = [INF]*(n+1)
        Fee_list[start] = 0
        while node_list:
            fee,node = heapq.heappop(node_list)
            if fee > Fee_list[node]:
                continue
            if node == end:
                return fee
            for next_node in graph[node]:
                temp_fee = fee + graph[node][next_node]
                if Fee_list[next_node]> temp_fee:
                    Fee_list[next_node] = temp_fee
                    heapq.heappush(node_list,(temp_fee,next_node)) 
        return INF
        
    for k in total_node:
        answer = min(answer,distra(s,k)+distra(k,a)+distra(k,b))
    return answer

solution(7,3,4,1,[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]])

처음엔 다익스트라로 만들어서 풀었다. 이 풀이의 문제점은 한번했던 다익스트라를 계속하기 때문에, 시간이 오래걸리는 문제가 있었다.

import heapq


def solution(n, s, a, b, fares):
    answer = float('inf')
    INF = float('inf')
    graph = [[INF if x!=y else 0 for x in range(n+1)] for y in range(n+1)]
    for start,end,fee in fares:
        graph[start][end] = fee
        graph[end][start] = fee

    for mid in range(1,n+1):
        for start in range(1,n+1):
            for end in range(1,n+1):
                if graph[start][end] > graph[start][mid] + graph[mid][end]:
                    graph[start][end] = graph[start][mid] + graph[mid][end] 
        
    for k in range(1,n+1):
        answer = min(answer,graph[s][k]+graph[k][a]+graph[k][b])
    return answer

 위의 문제가 매번 다읷트라를 계산하는것을 벗어나기 위해 플로이드 와샬로 각 노드에서 다른노드까지의 최저비용을 갱신해놓고, 그 합의 최저값을 구하는 방식으로 했다.

import heapq

def solution(n, s, a, b, fares):
    answer = float('inf')
    INF = float('inf')
    graph = [{} for i in range(n+1)]
    for start,end,fee in fares:
        graph[start][end] = fee
        graph[end][start] = fee
    Fee_list = [[INF]*(n+1) for _ in range(3)]
    def distra(start,idx):
        nonlocal graph,n,Fee_list
        node_list = []
        heapq.heappush(node_list,(0,start))
        Fee_list[idx][start] = 0 
        while node_list:
            fee,node = heapq.heappop(node_list)
            if fee > Fee_list[idx][node]:
                continue
            for next_node in graph[node]:
                temp_fee = fee + graph[node][next_node]
                if Fee_list[idx][next_node]> temp_fee:
                    Fee_list[idx][next_node] = temp_fee
                    heapq.heappush(node_list,(temp_fee,next_node)) 
    distra(s,0)
    distra(a,1)
    distra(b,2)
    for mid in range(1,n+1):
        temp = Fee_list[0][mid] + Fee_list[1][mid] + Fee_list[2][mid]
        if answer > temp:
            answer = temp
    return answer


solution(7,3,4,1,[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]])

마지막은 www.youtube.com/watch?v=FX9n1PFv2K4 유튜브의 barkingdog님의 풀이를 참조해서 푼 방식이다.

제일 첫번째의 매번 다익스트라를 하던것을 총 3번의 다익스트라로 그 값들을 전부 저장해놓고 푸는 방식이다.

자세한 설명은 유튜브를 참조하길 바란다.

from itertools import combinations
from collections import Counter
def solution(orders, course):
    answer = []
    orders = list(map(sorted,orders))
    for course_cnt in course:
        temp = []
        for order in orders:
            temp += combinations(order,course_cnt)
 
        dict_item = Counter(temp)
        if dict_item:
            max_value = max(dict_item.values())
            max_dict = dict_item.most_common()
            if max_value > 1:
                for key,value in max_dict:
                    if value < max_value:
                        break
                    else:
                        answer.append(''.join(key))
    answer.sort()
    return answer

이 문제는 Counter와 combination 모듈을 이용해서 쉽게 구했다.

각 메뉴마다 combinations을 구해주고, 그 값들을 temp라는 리스트에 임시 저장을 해준다. 그런뒤에 Counter라는 모듈을 이용해서, 갯수를 쉽게 세준게 만들어준다.

거기서 max값을 찾고, 그 max값과 같은것들만 정답에 넣어주고 마지막에 정렬을 해준다.

Counter 모듈은 welog.tistory.com/106 를 참조하면 된다.

def solution(new_id):
    answer = ''
    not_string = '~!@#$%^&*()=+[{]}:?,<>/'
    new_id = new_id.lower()
    for item in new_id:
        if item not in not_string:
            answer += item

    while '..' in answer:
        answer = answer.replace('..','.')
    
    
    if answer:

        if answer[0] == '.':
            answer = answer[1:] if answer != '.' else '.'
        if answer[-1] == '.':
            answer = answer[:-1]
    if not answer:
        answer = 'a'

    if len(answer) >= 16:
        answer = answer[:15]
    if answer[-1] == '.':
        answer = answer[:-1]
    while len(answer) <= 2:
        answer += answer[-1]


    return answer

매번 나오는 듯한 문자열 문제이다. 각 STEP에 맞춰서 진행하면 되는 문제였다.

# 매출하락 최소화

def solution(sales,links):
    N = len(sales)
    sales = [0]+sales
    tree = [[] for _ in range(N+1)]
    for parents,child in links:
        tree[parents].append(child)
    loss_sale = [[0]*2 for _ in range(N+1)]
    # loss_sale[x][0] = x번 노드가 참석하는 경우
    # loss_sale[x][1] = x번 노드가 불참석하는 경우
    def dfs(node):
        nonlocal loss_sale,tree,sales
        if not tree[node]:
            loss_sale[node][0] = sales[node]
            return

        for child_node in tree[node]:
            dfs(child_node)
            loss_sale[node][0] += min(loss_sale[child_node][0],loss_sale[child_node][1])

        
        loss_sale[node][0] += sales[node]
        atamp_loss = float('inf')
        for child_node in tree[node]:
            atamp_loss = min(loss_sale[child_node][0]-loss_sale[child_node][1],atamp_loss)
        loss_sale[node][1] = max(0,atamp_loss) + loss_sale[node][0] - sales[node]
    dfs(1)
    return min(loss_sale[1])

www.youtube.com/watch?v=FX9n1PFv2K4

BaaarkingDog 님의 풀이와 

카카오 공식블로그에 있는, tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/를 참조하여 푼 문제이다.

그러니 실질적으로, 내힘으로 푼 문제라 할순 없지만, 내가 잘 모르는 Tree-dp에 관련된 문제이고, 코드를 분석하면서, 이러한 문제 유형에 대해서 경험해보기 위해서 풀었다.

자세한 설명을 원하시는 분은 상단에 링크된 유튜브와 카카오 공식 블로그를 참조하길 바란다.

기본적인 풀이는 tree-dp에 관련된 문제였다. dp를 tree에 적용시킨 거고, dfs를 재귀방식으로 해서 푼 문제로 생각했다..

먼저 들어온 links에 대해서 부모노드에 자식노드를 추가해주는 작업을 했다.

그리고 index가 전부 1부터 시작하기 때문에 풀이의 용이함을 위해, sales 앞에 0을 추가해주었다.

이 상태에서 dfs를 통해, 매출하락 최소화를 구하는 작업을 해줬다.

loss_sale 이란 변수는 해당 노드가 워크샵에 참여유무에 따른 매출하락을 저장해놓은 변수이다.

ex ) loss_sale[x][0] 은 x번 노드가 워크샵에 참석하는 경우

      loss_sale[x][1] 은 x번 노드가 워크샵에 참석하지 않는 경우

dp는 작은단위부터 해야된다고 생각해서, 가장 끝단부터 하겠다.

1) 리프노드일 경우

  리프노드 일 경우엔, 자기자신이 참석하는 거 외에는 loss_sale을 갱신해줄만한 요소가 없다.

   loss_sale[leaf_node][0] = sales[leaf_node] 를 넣어주고 return 해주면 된다.

2) 리프노드가 아닐 경우

   리프노드가 아닐경우, 그 노드들은 팀원이면서 팀장이다. 여기서는 dfs를 들어갔을때, 팀장노드인 시점에서 들어가므로, 팀장노드라고 부르겠다.

   2-1) 팀장노드가 참석하는 경우

      > 팀장노드가 참석하는 경우에는 팀원노드들이 어떤 상태인지 상관 없기 때문에, 각 자식노드들의 참석 불참석했을          때 둘 중 최소값을 더해주면 된다.

      > 그리고 마지막으로 팀장노드의 매출 값을 저장해주면 된다.

      즉, 각 팀원노드마다  min(loss_sale[팀원노드][0],loss_sale[팀원노드][1]) 를 구해서 더해주고, 마지막에 팀장의 sales를 더해주면 된다.

   2-2) 팀장노드가 참석하지 않는 경우

       > 팀장 노드가 참석하지 않는 경우엔, 팀원 노드들 중에 한명이 무조건 참석을 해야한다. 그렇다면 매출하락폭이 최소화가 될려면 불참이었을때와 참여했을때의 loss_sale을 비교해서 그 차이가 최소값인 것을 찾아서 그 팀원노드을 선택하면 된다. 그 팀원이 불참이였다가, 참여로 전환시키는 것이기때문에 그 값을 더해주면 된다.

       > 여기서 max(0,atamp_loss)라고 해준 이유는 카카오 공식문서에서 나온 설명 마지막 부분과 부합된다.

          만약 팀원노드 A가 있다고 했을때,

          팀원노드 A가 팀장인 팀에서 최소가 되는 경우가, 팀원노드 A가 참석을 했을 때라고, 하면,

          위에서 구한, loss_sale[팀원노드 A의 부모노드][0]에 포함이 되어있을것이고, 이미 A라는 팀원이 참석한것이기

          때문에, 더해줄 필요성이 없다.

          그래서 팀원노드 A의 loss_sale은 참석했을때 loss_sale[팀원노드A][0] 보다 loss_sale[팀원노드A][1]이

           더 클 것이기 때문에 음수가 나오므로, max를 통해 0과 비교하여 음수를 방지해 주는 것이다.

        > 이렇게 참석과 불참석의 차이가 최소가 되는 노드를 선택하고 그 값에 팀장노드가 참석했을때의 값에서

           팀장노드가 참석을 안하기 때문에, 팀장노드의 매출을 빼주면 된다.

위와 같은 과정을 거친 후 CEO인 1번노드의 loss_sale의 최소값을 출력해주면 된다.

이 문제는 풀이를 보면서 풀었지만, tree와 dp에 대한 개념이 잡히지 않고서는 쉽게 풀 수 없는 문제 인것같다.

평소에도 가장 어려워하는 알고리즘이 dp와 tree이기때문에, 어려웠고, 그 2개가 합쳐진거라 더 나에게 어려움으로 느껴졌다.

이 풀이를 보면서 느낀점은 dp를 풀때에는 소분화해서 풀어야 하고, 점화식을 찾아서 동적으로 해야한다.

상반기까지 남은기간이 얼마 안남았는데,

내가 평소에 약점인 tree, dp, 플로이드, prefix_sum, 투포인터,segement tree (거의 대부분이지만) 에 대해서 더 공부해야겠다.