Coding 공부

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에 맞춰서 진행하면 되는 문제였다.

import sys
input = sys.stdin.readline

def check_sdouk(x,y):
    index_set = set(range(1,10))
    occupy_set = set()
    for checky in range(9):
        if sdoku[x][checky]:
            occupy_set.add(sdoku[x][checky])
    for checkx in range(9):
        if sdoku[checkx][y]:
            occupy_set.add(sdoku[checkx][y])
    squarex = x//3*3
    squarey = y//3*3
    for checkx in range(squarex,squarex+3):
        for checky in range(squarey,squarey+3):
            if sdoku[checkx][checky]:
                occupy_set.add(sdoku[checkx][checky])
    return index_set-occupy_set



def sdoku_input(cnt):
    global check_max,result
    if cnt == check_max:
        result = [row[:] for row in sdoku]
        for row in result:
            print(*row)
        sys.exit()
        return
    else:
        a = check_sdouk(*check_list[cnt])
        if a:
            for number in a:
                sdoku[check_list[cnt][0]][check_list[cnt][1]] = number
                sdoku_input(cnt+1)
                sdoku[check_list[cnt][0]][check_list[cnt][1]] = 0
        else:
            return




sdoku = []
check_list = []
for x in range(9):
    input_list = list(map(int,input().split()))

    for y in range(9):
        if not input_list[y]:
            check_list.append((x,y))
    sdoku.append(input_list)
result = []
check_max = len(check_list)
sdoku_input(0)

재귀를 이용해서 풀었다.

sys.exit()를 통해 최초의 결과가 나오면 바로 나오게 해줬다.

import sys
input = sys.stdin.readline



def check(cnt):
    if cnt == len(check_list):
        for row in sdoku:
            print(*row)
        sys.exit()
    else:
        x,y = check_list[cnt]
        square_ind = x//3*3 + y//3
        for number in range(1,10):
            if row_index[x][number] + col_index[y][number] + square_index[square_ind][number] == 0:
                row_index[x][number] = 1
                col_index[y][number] = 1
                square_index[square_ind][number] = 1
                sdoku[x][y] = number
                check(cnt+1)
                row_index[x][number] = 0
                col_index[y][number] = 0
                square_index[square_ind][number] = 0
                sdoku[x][y] = 0


row_index = [[0]*10 for _ in range(9)]
col_index = [[0]*10 for _ in range(9)]
square_index = [[0]*10 for _ in range(9)]


sdoku = []
check_list = []
for x in range(9):
    input_list = list(map(int,input().split()))

    for y in range(9):
        if input_list[y]:
            row_index[x][input_list[y]] = 1
            col_index[y][input_list[y]] = 1
            square_ind = x//3*3 + y//3
            square_index[square_ind][input_list[y]] = 1
        else:
            check_list.append((x,y))
    sdoku.append(input_list)


check(0)

  위는 시간이 오래걸려서 개선된 버전이다. 이 방법은 col,row,square 마다 1~9까지의 list를 만들어놓고 거기서 바로 판단이 가능하게 바꿨다.

import sys
from collections import deque

input = sys.stdin.readline
def bfs():
    global INF,result
    stack = deque()
    stack.append((0,0,1,0))
    visited = [[[INF for z in range(2)] for _ in range(M)] for _ in range(N)]
    visited[0][0][0] = 1
    visited[0][0][1] = 1
    while stack:
        x,y,dis,wall_cnt = stack.popleft()
        if x== N-1 and y == M-1:
            if result > dis:
                result = dis
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx< N and 0<= ny < M:
                if visited[nx][ny][wall_cnt] > dis + 1 and wall_cnt <=1:
                    if arr[nx][ny] == '1' and not wall_cnt:
                        visited[nx][ny][wall_cnt] = dis + 1
                        stack.append((nx,ny,dis+1,wall_cnt+1))
                    elif arr[nx][ny] == '0':
                        visited[nx][ny][wall_cnt] = dis +1
                        stack.append((nx,ny,dis+1,wall_cnt))


N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(input()) for _ in range(N)]
wall = []
INF = float('inf')


result = INF
bfs()
if result == INF:
    print(-1)
else:
    print(result)

처음 풀었던 방식은 BFS를 하면서 방문을 했는지 안했는지를 하나의 축으로 추가해서 visited에 표시를 해주는 거였다.

import sys
from collections import deque


input = sys.stdin.readline


N,M = map(int,input().split())
arr = [list(input()) for _ in range(N)]
INF = float('inf')
distance_front = [[INF]*M for _ in range(N)]
distance_back = [[INF]*M for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
stack1 = deque()
stack2 = deque()
distance_front[0][0] = 1
distance_back[N-1][M-1] = 0

stack1.append((0,0))
stack2.append((N-1,M-1))

while stack1:
    x,y = stack1.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx <N and 0<= ny <M:
            if distance_front[nx][ny] == INF:
                distance_front[nx][ny] = distance_front[x][y] +1
                if arr[nx][ny] == '0':
                    stack1.append((nx,ny))

while stack2:
    x,y = stack2.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx <N and 0<=ny <M:
            if distance_back[nx][ny] == INF:
                distance_back[nx][ny] = distance_back[x][y] + 1
                if arr[nx][ny] == '0':
                    stack2.append((nx,ny))

result = distance_front[N-1][M-1]

for x in range(N):
    for y in range(M):
        if arr[x][y] == '1':
            result = min(result,distance_front[x][y]+distance_back[x][y])

if result != INF:
    print(result)
else:
    print(-1)

개선된 방식은 0,0에서 BFS를 돌리고, 목표지점인 (N-1,M-1)에서 BFS를 돌린다. 그리고 BFS를 돌리면서 최단거리를 저장해놓는다.

그리고 첫번째 돌린 BFS의 최단거리에서 목표지점까지의 최단거리를 구하고,

벽을 부셨을때 최단거리는 두개의 BFS의 합을 통해 구한다.

벽인 지점 (A,B)가 있으면, 첫번째 돌린 BFS의 (A,B)의 값과 두번째 돌린 BFS의 (A,B)을 합쳐주면 그 벽을 부셨을때의 최단 이동거리가 된다.

위와 같이 할려면 초기값을 주의해야하는데, 첫번째 BFS의 초기값은 1이고, 두번째 BFS는 0이다.

import heapq
import sys
input = sys.stdin.readline
N = int(input())

times = []
for _ in range(N):
    input_tuple = tuple(map(int,input().split()))
    heapq.heappush(times,input_tuple)

end_time_list = []
answer = 0
while times:
    start_time,end_time = heapq.heappop(times)
    if not end_time_list:
        answer += 1
        heapq.heappush(end_time_list,end_time)
    else:
        if end_time_list[0] > start_time:
            heapq.heappush(end_time_list,end_time)
            answer += 1
        else:
            heapq.heappop(end_time_list)
            heapq.heappush(end_time_list,end_time)
            
        
print(answer)

우선순위 힙을 응용한 문제이다. 먼저 (시작시간,종료시간)이 입력을 들어왔을때, 하나의 리스트에 저장을 해준다.

그리고 그것을 시작시간을 기준으로 정렬을 해준다.

그리고 하나씩 꺼내면서 판단을 해주면 된다.

end_time_list가 비워져있으면, 종료시간을 그냥 넣어준다.

end_time_list의 첫번째 값 즉. 가장 먼저 강의가 종료되는 시간보다, 현재 강의의 시작시간이 더 빠르면(작으면) 강의실을 여러개 구해야한다.

그러므로 answer를 +1 해주고, end_time_list에 현재 강의의 종료시간을 넣어준다.

그렇지 않을시에는, 강의실을 추가로 빌린필요가 없으므로, 가장 첫번째 값을 없애고, 현재 강의 종료시간을 end_time_list에 저장을 시켜준다.

end_time_list의 가장 첫번째 값은 가장 작은 값으로 유지되어야하므로, 우선순위 큐인 heapq를 사용했다.

import heapq
import sys
input = sys.stdin.readline

N = int(input())
class_list = []
for _ in range(N):
    start_time,end_time = map(int,input().split())
    class_list.append((start_time,end_time))

class_list.sort()
end_time_list = []
for start_time,end_time in class_list:
    if end_time_list:
        if end_time_list[0] <= start_time:
            heapq.heappop(end_time_list)
        heapq.heappush(end_time_list,end_time)
    else:
        heapq.heappush(end_time_list,end_time)

print(len(end_time_list))

좀 더 깔끔한 방식으로 푼 코드이다. 강의의 전체 정보를 저장하는 리스트는 굳이, 우선순위 힙을 쓸필요가 없으므로, 일반리스트로 쓰면서 정렬을 해줬다.

그리고 다른 변수로 answer를 저장하던걸 어차피, end_time_list의 길이와 답이 일치하므로, end_time_list의 길이로 답을 출력해주었다.

import heapq
import sys
input = sys.stdin.readline
def dijkstra(start_list,flag):
    global V,mac,star,INF,limit_x,limit_y,home_info
    distance = [INF]*(V+1)
    node_list = []
    limited = limit_x
    if flag:
        limited = limit_y
    for ind in start_list:
        distance[ind] = 0 
        heapq.heappush(node_list,(0,ind))

    while node_list:
        current_distance,node = heapq.heappop(node_list)
        if current_distance > limited:
            break
        if current_distance > distance[node]:
            continue
        for next_node in graph[node]:
            temp_distance = current_distance + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    for ind in home:
        if limited >= distance[ind]:
            home_info[ind][int(flag)] = distance[ind]
    

V,E = map(int,input().split())
INF = float('inf')
graph = [{} for _ in range(V+1)]

for _ in range(E):
    u,v,w = map(int,input().split())
    graph[u][v] = w
    graph[v][u] = w
mac_cnt,limit_x = map(int,input().split())
mac = set(map(int,input().split())) 
star_cnt,limit_y = map(int,input().split())
star = set(map(int,input().split()))

home = set(range(1,V+1))- mac - star
home_info = [[INF,INF] for _ in range(V+1)]

dijkstra(mac,False)
dijkstra(star,True)
min_sum = INF
for home_ind in home:
    if sum(home_info[home_ind]) < min_sum:
        min_sum = sum(home_info[home_ind]) 

if min_sum != INF:
    print(min_sum)
else:
    print(-1)

  다익스트라를 응용한문제이다. 처음에 집을 기준으로 하니 시간초과가 떴다.

그래서 역으로 맥도날드와 스타벅스를 각각을 기준으로 해서 다익스트라를 했다.

맥도날드를 각각의 시작점으로해서 집들하고 가장 짧은 거리를 갱신을 해주면된다. 그리고 이걸 저장할 때 x를 넘지 않는 경우에만 home_info 라는 리스트에 저장을 해줬다.

스타벅스도 동일하게 해주었다.

그리고 난뒤 마지막에 최저합을 구해서 출력을 해주었다.

N = int(input())


arr = list(map(int,input().split()))

start = 0
end = N-1
index_list = (arr[start],arr[end])
result = arr[end]+arr[start]

while start<end:
    temp = arr[end]+arr[start]
    if abs(result) > abs(temp):
        result = temp
        index_list = (arr[start],arr[end])
        if result == 0:
            break
    if temp >= 0:
        end -= 1
    else:
        start += 1


print(*index_list)

두 용액 문제하고 동일하다. 투 포인터를 이용해서 풀어주면 된다.