카카오 인턴십 2022

1. 등산코스 정하기

   다익스트라 알고리즘을 활용해야 겠다는 생각이 들었다.
   시작점 노드가 등산로 입구의 여러개의 노드이고
   계산하는 것이 최단 거리가 아니라 루트 안에서 제일 큰 거리를 구하는 것이고
   산봉우리에서의 다른 노드들까지의 거리는 계산하지 않아도 된다는 점이 달랐다
   즉 산봉우리까지 가는 길의 거리 계산이 돌아오는 거리 계산과 똑같을 것이라고 생각했다.

import heapq
import sys
INF = int(1e9)


def solution(n, paths, gates, summits):
    
    graph = [[] for _ in range(n+1)]
    distance = [INF] * (n+1)
    for path in paths :
        graph[path[0]].append((path[1],path[2]))
        graph[path[1]].append((path[0],path[2]))

    def dijkstra(starts):
        q= []
        for start in starts:
            heapq.heappush(q,(0,start))
            distance[start]=0
        while q:
            dist,now=heapq.heappop(q)
            if distance[now] < dist or now in summits:
                continue
            for i in graph[now]:
                cost= max(dist,i[1])
         
                if distance[i[0]] > cost:
                    distance[i[0]]=cost
                    heapq.heappush(q,(cost,i[0]))
                  
    dijkstra(gates)
   
    summits.sort(key=lambda x : (distance[x],x))
    return[summits[0],distance[summits[0]]]

2. 코딩테스트 공부
   DP를 활용해야 했던 문제였다
   문제를 풀어서 빠르게 다른 모든 문제를 풀 수 있느냐 vs 아니면 알고력이나 코딩력을 하나씩 올려야 하나
   이 기준을 명확히 잡고 풀면 되던 문제였던 것 같다.
   알고력과 코딩력을 인덱스로 하는 2차원 배열을 만들고 크기는 모든 문제를 다 풀 수 있는 수준 즉 problems에서 최대치를 추출해야 했다
   그러고 나서 구현만 하면 되는 문제였다

def solution(alp, cop, problems):
    maxalp=0
    maxcop=0
    for problem in problems:
        maxalp=max(maxalp,problem[0])
        maxcop=max(maxcop,problem[1])
    alp=min(maxalp,alp)
    cop=min(maxcop,cop)
    dp=[[151 for _ in range(maxcop+1)] for _ in range(maxalp+1)]
    
    dp[alp][cop]=0
    
    for i in range (alp,maxalp+1) :
        for j in range(cop,maxcop+1) :
            if i+1 < maxalp:
                dp[i+1][j]=min(dp[i][j]+1,dp[i+1][j])
            if j+1 < maxcop:
                dp[i][j+1]=min(dp[i][j]+1,dp[i][j+1])
            
            for alp_req,cop_req,alp_rwd,cop_rwd,cost in problems:
                if i >= alp_req and j >=cop_req :
                    next_alp=min(maxalp,i+alp_rwd)
                    next_cop=min(maxcop,j+cop_rwd)
                    dp[next_alp][next_cop]=min(dp[next_alp][next_cop],dp[i][j]+cost)
    return dp[-1][-1]
        
    answer = 0
    return answer

3.두 큐 합 같게 만들기

이 문제는 큐를 사용해도 되지만 사용하지 않아도 풀 수 있는 문제였다
시간초과에서 진땀을 뺀 거 같다..

from collections import deque

def solution(queue1, queue2):
    lan=len(queue1)*len(queue2)
    target_sum = (sum(queue1) + sum(queue2)) // 2
    left_sum = sum(queue1)
    right_sum = sum(queue2)
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    
    answer = 0
    if (left_sum + right_sum) % 2 !=0:
        return -1
    while queue1 and queue2 and answer<lan:
        if left_sum < right_sum:
            tmp = queue2.popleft()
            left_sum += tmp
            right_sum-= tmp
            queue1.append(tmp)
            answer += 1
        elif left_sum > right_sum:
            tmp= queue1.popleft()
            left_sum -= tmp
            queue2.append(tmp)
            right_sum+= tmp
            answer += 1
        else:
            return answer

    else:
        return -1