Coding 공부

import sys

sys.setrecursionlimit(20000)

def solution(k, num, links):
    left = sum(num)//k
    right = sum(num)
    N = len(num)
    degrees = [0 for _ in range(N)]
    for ind in range(N):
        if links[ind][0] != -1:
            degrees[links[ind][0]] += 1
        if links[ind][1] != -1:
            degrees[links[ind][1]] += 1
    root = -1
    for ind in range(N):
        if not degrees[ind]:
            root = ind
            break
    INF = float('inf')
    def check(node):
        nonlocal links,INF,dp,mid
        if links[node][0] == -1 and links[node][1] == -1:
            if num[node]<=mid:
                dp[node][0] = num[node]
                dp[node][1] = 1
            else:
                dp[node][0] = 0
                dp[node][1] = INF
        else:
            for ind in range(2):
                if links[node][ind] != -1:
                    check(links[node][ind])
            left_node = links[node][0]
            right_node = links[node][1] 
            if dp[left_node][0] + dp[right_node][0] + num[node] <= mid:
                dp[node][0] = dp[left_node][0] + dp[right_node][0] + num[node]
                dp[node][1] = dp[left_node][1] + dp[right_node][1] -1
                return
            if right_node == -1:
                if num[node] <= mid:
                    dp[node][0] = num[node]
                    dp[node][1] = dp[left_node][1] + 1
                else:
                    dp[node][0] = 0
                    dp[node][1] = INF

            else:
                if num[node] + min(dp[right_node][0],dp[left_node][0])<= mid:
                    dp[node][0] = num[node] + min(dp[right_node][0],dp[left_node][0])
                    dp[node][1] = dp[right_node][1] + dp[left_node][1]
                elif num[node] <= mid:
                    dp[node][0] = num[node]
                    dp[node][1] = dp[left_node][1] + dp[right_node][1] + 1
                else:
                    dp[node][0] = 0
                    dp[node][1] = INF

            



    while left+1<right:
        mid = (left+right)//2
        dp = [[0,1] for _ in range(N+1)]
        check(root)
        if dp[root][1]<=k:
            right = mid
        else:
            left = mid
    return right

풀기 힘들었던 문제이다.

이 문제는 트리 DP와 파라메트릭 서치를 활용한 문제로

k개의 그룹으로 나눌 수 있는 최소 값을 찾는것이다.

카카오 해설에서도 알수 있듯이 이분탐색으로 찾으면 되고,

이 이분 탐색의 중간값인 mid가 의미하는 것은 이 트리를 나눌 최대의 인원을 의미한다.

한 그룹의 인원이 mid가 넘어가지 않게 해주면 된다.

즉 mid의 값이 크면 k는 적게 나올것이고, mid의 값이 작으면 k보다 많게 나올 것이다.

우리는 left+1<right일때 끝나고

left일때 false이므로,

우리가 구하고자 하는 값은 right임을 알 수 있다.

문제에 들어가면,

가장 밑 노드에서부터 해주면 된다.

먼저 dp 테이블은 N*2의 크기로 해주었고,

dp[x][0] 은 x 노드에서의 최소 그룹인원의 수

dp[x][1] 은 x 노드에서의 그룹의 개수를 의미한다.

각 노드는 처음에 하나의 그룹이므로, dp[x][0]은 0으로 dp[x][1]은 1로 초기화를 해주었다.

총 4가지 경우가 있을것이다.

1. 자식노드 2개에 누적된 그룹인원과 현재노드의 인원과  더해도 mid보다 작거나 같다.

    그러면 dp[parent][0] = num[parent] + dp[left_node][0] + dp[right_node][1]이 될것이다.

    그리고 그룹의 수는 자식노드의 그룹의 수를 더해준 것에서 -1을 해준다.

    이러는 이유는 우리가 각 노드를 하나의 그룹으로 생각했기 때문에, 처음에 1로 전부 초기화 되어 있어서 그런다.

   자식노드와 현재그룹을 더해서 한개의 그룹이 된 것이므로 - 1을 해준다.

2. 자식노드 둘 중 1개 그룹인원과  현재 노드의 인원과 더하면 mid보다 작거나 같다.

   이럴때에는 그룹인원이 많은쪽의 간선을 끊는것과 마찬가지 이므로

   dp[parent][0] = num[parent] + min(dp[left_node][0], dp[right_node][1])

  을 해주고, 그룹은 두 자식노드의 그룹인원을 더해주면 된다.

3. 현재 그룹인원의 mid보다 작거나 같고, 자식노드들의 인원을 더하면 mid보다 크다.

   이럴 경우는 간선을 전부 끝는 것이다.

   그래서 dp[parent][0] = num[parent]를 해주고,

   그룹의 수는 1개를 더 더해주면 된다.

4. 현재 그룹의 인원의 mid보다 크다.

   이럴때에는 어떤 방도로도 mid보다 작거나 같은 그룹으로 나눌수 없으므로, 그룹인원의 수를 0으로 초기화 해주고, 그룹의 수를 INF로 해준다.

이 문제는 평소 코에서 나오지 않는 트리dp 문제인데다가, 이분탐색까지 활용해야되서 어려웠던 문제였다.

dp 테이블을 설계하는 것부터, 그룹의수가 k이면서 최소의 그룹인원 수를 어떻게 찾아하는지 생각하기 어려운 문제였다.

이 문제는 카카오 시험이 끝난뒤, 알고리즘 고수분들을 이야기를 통해, 어떻게 풀어야할지 감을 잡았고,

문제가 나오고 실제로 푸는데에도 시간이 오래걸린 문제였다.

이 문제가 다시 나오면 풀수 있다는 확신은 없지만, 한번 경험해봤으니 이러한 문제도 있다라는 것을 배운점에 만족했다.

import heapq

def solution(n, start, end, roads, traps):
    answer = 0
    INF = float('inf')
    dp = [[INF for _ in range(n+1)] for _ in range(1<<len(traps))]
    traps_index ={value:ind  for ind,value in enumerate(traps) }
    node_list = []
    graph =[[] for _ in range(n+1)]

    for road in roads:
        x,y,pay = road
        graph[x].append([y,pay,0])
        graph[y].append([x,pay,1])

    heapq.heappush(node_list,(0,start,0))
    dp[0][start] = 0
    while node_list:
        cur_time,cur_node,state = heapq.heappop(node_list)
        if end == cur_node:
            answer = cur_time
            break
        if dp[state][cur_node] < cur_time:
            continue
        for next_node,pay,flag in graph[cur_node]:
            next_state = state
            if cur_node in traps:
                if next_node in traps:
                    cur_flag = ((1&(state>>traps_index[cur_node])) + 
                    (1&(state>>traps_index[next_node])))%2
                    next_state = state^(1<<traps_index[next_node])
                else:
                    cur_flag = (1&(state>>traps_index[cur_node]))
            else:
                if next_node in traps:
                    cur_flag =  (1&(state>>traps_index[next_node]))
                    next_state = state^(1<<traps_index[next_node])
                else:
                    cur_flag = 0
            
            if cur_flag == flag:
                if dp[next_state][next_node] > cur_time + pay:
                    dp[next_state][next_node] = cur_time + pay
                    if next_node in traps:
                        heapq.heappush(node_list,(dp[next_state][next_node], next_node,next_state ))
                    else:
                        heapq.heappush(node_list,(dp[next_state][next_node],next_node,next_state))

    return answer

이 문제를 핵심은 트랩을 밟았을 때의 상태를 어떻게 저장할 것인가.

저장한 그 상태를 통해 현재 길의 상태를 어떻게 알 수 있을가인가.

이 문제는 총 4가지 경우가 있다고 볼 수 있다.

트랩이 아닌  곳 -> 트랩이 아닌곳

트랩이 아닌 곳 -> 트랩인 곳

트랩인 곳 - > 트랩이 아닌곳

트랩인 곳 -> 트랩인 곳

이렇게 총 4가지 경우가 있을거고, 각각의 상태를 구분해서, 하면 된다.

우리는 먼저 주어진 경로들을 2가지 형태로 저장해놔야한다.

원래 주어진 정방향과, 이게 뒤집혔을때 가는 역방향이다. 이걸 나는 (다음노드, 시간, 상태) 로 넣어놨다.

0이면 정방향

1이면 역방향을 의미하는 식으로 넣어놨다.

트랩은 최대10개 밖에 없고, 트랩의 상태는 비트마스킹을 통해 나타낼수있다.

그렇게 하기 위해 각각의 trap들의 index로 각자의 위치를 매핑시켜줬다.

그러면 인제부터 각위치의 비트가 1이면 해당 위치의 트랩이 활성화 된 상황이고, 비활성화일때는 0이다.

그리고 우리는 각 상태에서 다익스트라를 돌리는 것이기 때문에 최대 (2**10) * N개의 distance 테이블을 만들어놓고 탐색을 하면 된다.

원래의 다익스트라와 비슷하게 하지만, 우리는 state를 통해 현재 길을 이용할 수 있는지 없는지 판별을 해줘야한다.

한 그래프에 정방향, 역방향을 전부 넣어놨기 때문에, state를 통해서 해당 길을 이용할 수 있는지 찾아야한다.

먼저 가장 쉬운

현재 노드가 트랩이 아닐때이다.

만약 다음 노드가 트랩이 아니라면, 이 길은 항상 정방향이다. 그러므로 저장해놓길 0으로 저장해놓은 길들만 이용이 가능하다.

만약 다음 노드가 트랩이라면, state를 통해 해당 트랩이 활성화 되어있는지 판별을 하면 된다.

판별하는 방법은 현재 state를 해당 트랩의 index만큼 >> 오른쪽으로 비트 이동을 시킨다. 그리고 1과 & 연산을 하면 된다.

이게 1이면 활성화가 된 상태이고, 아니면 비활성화 상태이다.

다음은 현재노드가 트랩일때이다.

현재노드가 트랩이고, 다음노드가 트랩이 아닐때에는 위와 동일하므로 넘어가겠다.

가장 많이 고민했던, 현재노드와 다음노드가 전부 트랩일때이다.

이때는 총 4가지 경우가 생긴다.

1. 현재노드 비활성화 다음노드 비활성화

2 .현재노드 활성화 다음노드 비활성화

3. 현재노드 비활성화 다음노드 활성화

4. 현재노드 활성화 다음노드 활성화

총 4가지 경우가 생긴다.

1번의 경우는 둘다 활성화가 안되어있기 때문에 정방향인 길들만 가면된다.

2,3번은 동일하고, 한쪽만 활성화 되어있으면, 그 길은 한번 뒤집힌거기 때문에 역방향인 길들만 가면 된다.

4번은 현재노드 다음노드 전부 활성화 되어있을때이다.

이때는 이 길이 2번 뒤집힌거기 때문에, 정방향인 길들만 가면된다.

그래서 나는 

(    ( 1 & (state>>traps_index[cur_node]) ) + ( 1&( state>>traps_index[next_node]) ) )%2

2개의 상태를 더해서 2로 나눈 나머지로 해서 정방향, 역방향을 구분을 해줬다. 이 외에도 xor 연산을 해도 된다.

우리는 이렇게 해서 해당 길이 갈 수 있는 길인지 아닌지 판별을 했다.

나머지는 다익스트라와 동일하게 하면되는데, 

그리고 현재의 상태와 비교하는게 아니라, 다음의 상태와 비교를 해서 판별을 해주었다.

만약 다음 노드가 트랩이라 한다면, 그 트랩은 활성화가 된 상태인거고, 그때 최소값으로 들어가야한다고 생각했다

그래서 각 현재 시간과 다음노드까지 걸리는 시간은 현재 state가 아닌, 만약 다음노드가 트랩이라면, 트랩의 상태에 따라, 변화된 state로 비교를 해서 구현을 했다.

def check(t,result):
    if len(result):
        if result[-1] == t:
            result.pop()
            return 2
        else:
            result.append(t)
            return 0
    else:
        result.append(t)
        return 0


def solution(board, moves):
    answer = 0
    lens = len(board)
    result = []
    for k in moves:
        for t in range(lens):
            if board[t][k-1]:
                answer += check(board[t][k-1],result)
                board[t][k-1] = 0
                break
            
    return answer

시뮬레이션을 통해 해주면 간단한 문제이다.

가장 끝에 있는 경우와 아닌경우를 비교해서 해주면 된다.

from itertools import permutations
from collections import deque
def outOfrange(x,y):
    if 0 > x or x >3 or y<0 or y>3:
        return True
    return False

def dfs(start,end,copy_board):
    dp = [[-1]*4 for _ in range(4)]
    dp[start[0]][start[1]] = 0
    stack = deque()
    stack.append((start[0],start[1]))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            repeat = 0
            while True:
                nx = x + dx[i]*repeat
                ny = y + dy[i]*repeat
                if outOfrange(nx+dx[i],ny+dy[i]) or (repeat!=0 and copy_board[nx][ny]):
                    break
                repeat += 1
            for re in (1,repeat):
                nx = x + dx[i] * re
                ny = y + dy[i] * re
                if outOfrange(nx,ny):
                    continue
                if dp[nx][ny] == -1:
                    dp[nx][ny] = dp[x][y] + 1
                    stack.append((nx,ny))
                    if dp[end[0]][end[1]] != -1:
                        return dp[end[0]][end[1]]
    return dp[end[0]][end[1]]



def find_command(x,y,find_card,copy_board):
    dis1 = dfs((x,y),find_card[0],copy_board)
    dis2 = dfs(find_card[0],find_card[1],copy_board)
    return dis1+dis2




def solution(board, r, c):
    answer = float('inf')
    card_list = [[] for _ in range(7)]
    card_numbers = set()
    for x in range(4):
        for y in range(4):
            if board[x][y]:
                card_list[board[x][y]].append((x,y))
                card_numbers.add(board[x][y])

    card_cnt = len(card_numbers)
    for combi in permutations(card_numbers):
        predict_dict = {}
        for k in range(1<<card_cnt):
            distance = 0
            mouse_cursor_x = r
            mouse_cursor_y = c
            copy_board = [row[:] for row in board]
            temp = ''
            for ind,num in enumerate(combi):
                start = int(bool((k&1<<(ind))))
                end = (start+1)%2
                temp += str(start)
                find_card = [card_list[num][start],card_list[num][end]]
                if not predict_dict.get(temp):
                    distance += find_command(mouse_cursor_x,mouse_cursor_y,find_card,copy_board)
                    predict_dict[temp] = distance
                else:
                    distance = predict_dict[temp]
                mouse_cursor_x = card_list[num][end][0]
                mouse_cursor_y = card_list[num][end][1]
                copy_board[card_list[num][start][0]][card_list[num][start][1]] = 0
                copy_board[card_list[num][end][0]][card_list[num][end][1]] = 0
                if distance > answer:
                    break
            if answer > distance:
                answer = distance
    return answer+2*card_cnt


a = solution([[1,0,2,0],[6,2,4,0],[0,0,1,0],[6,0,0,4]],1,0)
print(a)

문제 자체는 BFS+순열+조합으로 간단해보였지만, 구현하는데 난이도가 컸던 문제였다.

기본 풀이 자체는 다음과 같다.

카드번호 1,2,3이 있다고 하면

1,2,3을 순열로 먼저 없앨 카드별 순서를 정해준다.

그리고 각 카드는 2장씩 있으므로, A,B 가 있다고 치면

1A->1B

1B->1A는 다를 것이다.

이 모든 경우를 돌려서 결과를 얻는 것이다.

그래서 먼저 나는 card_numbers에 이 보드에 있는 카드번호들을 저장해두고 permutations 모듈을 사용해서 순열을 만들었다 그리고 난뒤, 카드의 앞뒷면을 정해주기 위해 조합을 만들었다.

만약 우리가 카드가 3장이 있다고 하면 이 카드의 앞뒷면을 만들수 있는 가짓수는

000

001

010

011

100

101

110

111

이런식으로 총 8가지가 있을수 있다. 위의 가지수를 각비트로 봐보면 0~7까지인걸 알수 있다. 그러므로 저는 카드의 개수가 N이라고 하면, 2**N 만큼 range를 돌리고, 각 permutations으로 나오는 각각의 카드 index와 비트연산을 해서, 해당 카드의 앞뒷면의 순서를 결정해주었다.

이렇게 한뒤 현재 커서위치 -> 먼저 찾을 카드위치 -> 나중 찾을 카드위치 순으로, bfs를 돌렸다.

bfs를 돌릴때, ctrl 이동과 일반적인 한칸이동을 동시에 시행했다. 범위 밖을 나가던지, 아니면 카드가 있는 위치이던지, 그 위치까지의 길이를 기억해놓은뒤, 그 만큼을 dp라는 visited를 담당하는 행렬에 저장을해주었다. 그리고 우리가 찾는 목적지에 도착하면, return 해주는 방식으로 했다.

이렇게 bfs를 전부 돌린뒤에는 copy한 board에서 우리가 현재 뒤집은 카드들의 정보를 0으로 바꿔주고, 마우스 커서위치는 마지막 카드위치로 바꿔주는 작업을 해준다.

위 풀이 방식은 아슬아슬하게 시간을 통과한지라 여러부분에서 시간을 줄여주었다. 위에서 했듯이 bfs에서 매번 도착지점을 판별해주는 것이 첫번째 방법이었고, distance가 저장된 answer 보다 커지면 탐색을 중단해주는것도 그 방안이었다.

이렇게 구한 answer에 현재 카드의 종류의 2배만큼 더해서 출력해주면된다.

from collections import deque
import functools
def solution(board,r,c):
    card_dict = [[] for i in range(7)]
    card_tuple = set() 
    for x in range(4):
        for y in range(4):
            if board[x][y]:
                card_dict[board[x][y]].append((x,y))
                card_tuple.add(board[x][y])
    card_tuple = tuple(card_tuple)

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    def outOfrange(x,y):
        if 0 > x or x >3 or y<0 or y>3:
            return True
        return False

    @functools.lru_cache(maxsize=None)
    def bfs(s,t,cards):
        if s == t:
            return 0
        stack = deque()
        stack.append((s[0],s[1],0))
        visited = set()
        while stack:
            x,y,cnt = stack.popleft()
            for i in range(4):
                repeat = 0
                while True:
                    nx = x + dx[i]*repeat
                    ny = y + dy[i]*repeat
                    if outOfrange(nx+dx[i],ny+dy[i]) or (repeat != 0 and board[nx][ny] in cards):
                        break
                    repeat += 1
                for re in [1,repeat]:
                    nx = x + dx[i]*re
                    ny = y + dy[i]*re
                    if outOfrange(nx,ny):
                        continue
                    if (nx,ny) == t:
                        return cnt + 1
                    if (nx,ny) not in visited:
                        visited.add((nx,ny))
                        stack.append((nx,ny,cnt+1))

    @functools.lru_cache(maxsize=None)
    def find_card_short_count(cur_position,cards):
        if len(cards) == 0:
            return 0
        min_distance = float('inf')
        for pick_card in cards:
            position1,position2 = card_dict[pick_card]
            remain_cards = tuple(card for card in cards if card != pick_card)
            direction1 = bfs(cur_position,position1,cards) + bfs(position1,position2,cards) + find_card_short_count(position2,remain_cards)
            direction2 = bfs(cur_position,position2,cards) + bfs(position2,position1,cards) + find_card_short_count(position1,remain_cards)
            min_distance = min(min_distance,direction1,direction2)
        return min_distance

    answer = len(card_tuple)*2 + find_card_short_count((r,c),card_tuple)
    return answer


a = solution([[1, 0, 0, 3], [2, 0, 0, 0], [0, 0, 0, 2], [3, 0, 1, 0]], 1, 0)
print(a)

위의 풀이 대신 이 풀이는 프로그래머스의 다른사람풀이를 보고 공부하면서 쓴 풀이다.

자세한 설명은 http://www.teferi.net/ps/problems/programmers/72415 이 링크를 참조하길 바란다.

기본적인 풀이는 비슷하다. 대신 이 풀이는 위에서 복잡하게 비트연산을 통해 결정하는 것이 아닌, 재귀함수를 통해, 순열과 조합을 구현했고, functools.lru_cache를 통해 메모라이즈를 해주었다.

이 두 방식을 통해 시간이 획기적으로 줄어들었다.

이 풀이는 크게 2가지의 함수로 나뉠수 있다. find_card_short_count라는 함수와 bfs 함수이다.

bfs는 A->B까지 가는 최소 명령어를 찾아주는 것이다. 여기서 카드의 위치를 판단하는것은 cards라는 tuple을 통해, 있는지 판별을 해준다.

여기서 중요한것은 find_card_short_count라는 함수이다. 이 함수의 역할은 재귀를 통해 순열을 만드는 것이다.

cur_position은 현재 커서의 위치이고, cards는 현재 남아있는 카드들의 번호들이다.

이 cards를 반복문을 돌리면서 그 카드를 제거할 카드라 생각하고, cards에서 현재 선택한 card를 제외한 나머지 카드들을 remain_cards로 남겨준다.

위에서 설명했던 것처럼 한 카드에서도 먼저 제거할 카드를 선택을 해야한다. 그 방법으로 direction1과 direction2로 나뉘어서 해주었다.

한 카드에서 position1 과 position2가 있다고 하면 제거할 수 있는 방법은 두가지이다.

현재 커서위치 -> position1까지의 거리를 구해주고 position1 -> position2 까지의 거리를 구해준다.
그러면 마지막 커서의 위치는 position2가 되고 position2와 remain_cards를 가지고 find_card_short_count를 해주면 된다.

이런 방식으로 현재 커서 위치 -> position2 -> position1도 똑같이 해준다.

direction1 = bfs(cur\_position,position1,cards) + bfs(position1,position2,cards) + find\_card\_short\_count(position2,remain\_cards)

direction2 = bfs(cur\_position,position2,cards) + bfs(position2,position1,cards) + find\_card\_short\_count(position1,remain\_cards)

이 식들이 위에서 설명해준것을 구현한 것이다.

여기서 중요한 역할을 하는 것은 functools.lru_cache 라는 데코레이터이다.

이 데코레이터의 역할은 함수의 호출을 기억해주는 것이다. 똑같은 입력값이 들어온 함수들을 기억해서, 다음번에 호출이 되는 경우 함수를 한번더 실행하는 것이 아닌, 기억한 결과값을 그대로 주는 것이다.

그렇기 때문에 이 데코레이터를 썼을 때, 메모라이즈를 해준것이기 때문에, 재귀함수를 쓰면서도 시간을 줄일 수 있다.

다음과 같이 시간을 100ms 이하로 줄일 수 있다.

functools.lru_cache를 쓰지 않으면 시간의 압박이 크다.

위의 풀이가 아닌 DP를 활용한 풀이를 보고 싶은 분들은 https://www.youtube.com/watch?v=FX9n1PFv2K4 해당 유튜브를 참조하길 바랍니다.

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 를 참조하면 된다.