JH 개발 블로그

다익스트라, 플로이드와샬 두가지 알고리즘으로 문제를 풀 수 있습니다.

다익스트라

import heapq

def dijkstra(s,i):
    global n,graph
    hq = [(s,0)]
    heapq.heapify(hq)

    visited = [float('inf')]*(n+1)
    visited[s] = 0

    while hq:
        now_node,now_fare = heapq.heappop(hq)
        if now_fare > visited[now_node]:
            continue
        for fare,node in graph[now_node]:
            sum_fare = now_fare+fare
            if sum_fare < visited[node]:
                visited[node] = sum_fare
                heapq.heappush(hq,(node,sum_fare))
    return visited[i]

def solution(n, s, a, b, fares):
    global graph
    graph = [[] for _ in range(n+1)]
    for c,d,f in fares:
        graph[c].append([f,d])
        graph[d].append([f,c])
    answer = float('inf')
    for i in range(1,n+1):
        answer = min(answer,dijkstra(s,i)+dijkstra(i,a)+dijkstra(i,b))
    return answer

플로이드와샬

def solution(n, s, a, b, fares):
    graph = [[float('inf')]*(n+1) for _ in range(n+1)]

    for i in range(1,n+1):
        graph[i][i] = 0

    for c,d,f in fares:
        graph[c][d] = f
        graph[d][c] = f

    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

    answer = float('inf')

    for i in range(1,n+1):
        answer = min(answer,graph[s][i]+graph[i][a]+graph[i][b])

    return answer

다익스트라 알고리즘은 한 노드에서 모든 다른 노드까지의 최단거리를 구하지만,

플로이드 와샬 알고리즘은 한 노드에서 모든 다른 노드까지의 최단거리를 모든 노드에 대해 구합니다.

다익스트라 알고리즘은 현재 상태에서 방문하지 않은 노드중 거리가 가장 가까운 노드 먼저 방문하면서 최단거리를 구합니다. 

플로이드 와샬 알고리즘은 i노드에서 j노드로 한번에 가는 거리와 i노드에서 k노드를 거쳐 j노드를 가는 거리를 비교하여 최단거리를 갱신해 줍니다.

from bisect import bisect_left
from collections import defaultdict

def solution(info, query):
    candidates = defaultdict(list)
    answer = []

    for i in range(len(info)):
        temp = info[i].split()
        for i in [temp[0], '-']:
            for j in [temp[1], '-']:
                for k in [temp[2], '-']:
                    for l in [temp[3], '-']:
                        candidates[(i,j,k,l)].append(int(temp[4]))

    for c in candidates:
        candidates[c].sort()


    for i in range(len(query)):
        temp = query[i].split()
        conditions = (temp[0],temp[2],temp[4],temp[6])
        score = temp[7]
        answer.append(len(candidates[conditions]) - bisect_left(candidates[conditions],int(score)))

    return answer

만약 query의 요소중 하나가 "- and backend and senior and chicken 150" 이라면,

"cpp and backend and senior and chicken 150"

"java and backend and senior and chicken 150"

"python and backend and senior and chicken 150"

위 세개의 조건을 물어보는것과 같습니다.

따라서 딕셔너리[(개발언어,직군,경력,소울푸드)] 에 점수를 넣고, 각 항목 하나씩  '-'로 변경한 후에도 점수를 넣어줍니다.

그 후, 효율성 테스트 통과를 위해 딕셔너리를 정렬 해준뒤 이분탐색하여 수를 구해줍니다.

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []
    temp = []
    for order in orders:
        temp.append(sorted(order))
    orders = temp

    for size in course:
        temp = []
        for order in orders:
            temp += combinations(order,size)
        temp = Counter(temp).most_common()
        for menu, cnt in temp:
            if cnt >= 2 and cnt >= temp[0][1]:
                answer.append(menu)
            else:
                break

    return sorted(''.join(x) for x in answer)

1. orders 리스트의 각 주문음식은 정렬되어 있지 않기 때문에 먼저 정렬해 줍니다.

2. course 리스트의 사이즈 별로 각 주문음식들의 조합을 구해줍니다.

3. Counter 함수를 통해 주문 횟수가 2번 이상이면서 가장 많이 주문된 메뉴를 answer 리스트에 추가합니다.

4. answer 리스트를 정렬합니다.

import re

def solution(new_id):
    new_id = re.sub('[^a-z\d\-_.]','',new_id.lower())
    new_id = re.sub('\.\.+','.',new_id)
    new_id = re.sub('^\.|\.$','',new_id)
    if new_id == '':
        new_id = 'a'
    new_id = re.sub('\.$','',new_id[:15])
    while len(new_id) < 3:
        new_id += new_id[-1]
    return new_id

1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
     만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

import heapq
import sys

N, K = map(int, sys.stdin.readline().split())
jewelryList = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
bagList = [int(sys.stdin.readline()) for _ in range(K)]
jewelryList.sort()
bagList.sort()

result = 0
temp = []

for bagWeight in bagList:
    while jewelryList and bagWeight >= jewelryList[0][0]:
        heapq.heappush(temp, -heapq.heappop(jewelryList)[1])  # Max heap

    if temp:
        result += heapq.heappop(temp)
    elif not jewelryList:
        break

print(-result)

힙은

1. 데이터가 지속적으로 정렬이 되어야 할 때
2. 데이터의 삽입 / 삭제가 빈번히 일어날 때
풀이시간을 많이 줄여줍니다.

만약 temp가 비어있는데, 보석리스트까지 비어있다면 종료합니다.
(가방의 개수가 많이 남아있어도 넣을 보석이 없으면 의미가 없습니다.)

import sys
import heapq
input = sys.stdin.readline
n = int(input())
li = [list(map(int,input().split())) for _ in range(n)]
li.sort(key=lambda x:x[1])
temp = []

for p,d in li:
    heapq.heappush(temp,p)
    if len(temp) > d:
        heapq.heappop(temp)
print(sum(temp))