Coding 공부

import sys
input = sys.stdin.readline




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

for _ in range(E):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C
INF = float('inf')
visited = [False]*(V+1)
distance = [INF]*(V+1)
distance[1] = 0

node_list = [(1,0)]
cnt = 1
result = 0
while cnt <V:
    node, dis = node_list.pop()
    current_min_dis = INF
    current_min_node = -1
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] =  graph[node][next_node]

    for ind in range(1,V+1):
        if current_min_dis > distance[ind] and not visited[ind]:
            current_min_node = ind
            current_min_dis = distance[ind]
    node_list.append((current_min_node,current_min_dis))
    result += current_min_dis
    cnt += 1

print(result)

첫 풀이는 다익스트라랑 비슷한 프림 알고리즘을 이용한 풀이였다. 하지만 해당 풀이는 실행시간이 오래걸려서 또 다른 방식으로 풀었다.

import sys
import heapq

input = sys.stdin.readline
V,E = map(int,input().split())

graph = [{} for _ in range(V+1)]

for _ in range(E):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C
INF = float('inf')
distance = [INF]*(V+1)
visited = [False]*(V+1)
node_list = []
distance[1] = 0
heapq.heappush(node_list,(0,1))
result = 0
while node_list:
    key,node = heapq.heappop(node_list)
    if visited[node]:
        continue
    visited[node] = True
    result += key
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            heapq.heappush(node_list,(graph[node][next_node],next_node))
            distance[node] = graph[node][next_node]
print(result)

두번째는 프림 알고리즘이지만, heapq를 활용한 풀이였다. 위의 방식과 똑같지만, distance가 갱신될때에만을 판단하고, 그때 node_list에 추가하는 방식이었다.

import sys

input = sys.stdin.readline
def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
    if x > y:
        x,y = y,x
    make_set[y] = x

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]




V,E = map(int,input().split())

grpah = sorted([list(map(int,input().split())) for _ in range(E)],key=lambda x : x[2],reverse=True)

make_set = [i for i in range(V+1)]

cnt = 1 
result = 0

while cnt <V:
    p1,p2,weight = grpah.pop()
    if find_parent(p1) != find_parent(p2):
        union(p1,p2)
        result += weight
        cnt += 1

print(result)

크루스칼 알고리즘으로 푼 방식이다. 크루스칼 알고리즘이 편한사람들은 금방 푼다고하는데, 크루스칼 알고리즘에 익숙하지 못해서 시간이 오래걸렸다.

많이 실패했던것은 make_set에 저장된 parent_node로 비교를 했을때 틀렸다. find_parent 이후에, 루트노드가 바뀐 경우 make_set에 저장된 모든 parent들이 root_node로 갱신되는것이 아니기 때문에, 문제가 생겼었다.

프림 알고리즘과 크루스칼 알고리즘은 자주 쓰이므로 좀 더 익숙해져야겠다.

def dfs(x,y):
    global N,M
    if x == N-1 and y == M-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] < arr[x][y]:
                    dp[x][y] += dfs(nx,ny)
        return dp[x][y]



import sys

input = sys.stdin.readline

N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*M for _ in range(N)]
print(dfs(0,0))

DP 와 DFS가 결합된 문제였다. 최소로 도달한거리를 DP에 저장해서 얻는것이었다. 마지막 우리가 도달해야하는 위치만 초기값을 1로 주고, 나머지는 전부 0으로 초기화한뒤 역으로 계싼해서 오는것이다.

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

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이다.