Coding 공부

from collections import deque

N = int(input())
if N == 1:
    print(0)
    print(1)
else:
    dp_dict = {N:-1}
    stack = [N]
    cnt = 0
    while stack:
        new_stack = []
        for num in stack:
            if not (num%3 or dp_dict.get(num//3)):
                dp_dict[num//3] = num
                new_stack.append(num//3)
            if not (num%2 or dp_dict.get(num//2)):
                dp_dict[num//2] = num
                new_stack.append(num//2)
            
            if not dp_dict.get(num-1) and num>1:
                dp_dict[num-1] = num
                new_stack.append(num-1)
        cnt += 1
        if 1 in new_stack:
            break
        stack = new_stack[:]
    result = []

    find_num = 1
    print(cnt)
    while True:
        result.append(find_num)
        find_num = dp_dict[find_num]
        if find_num == -1:
            break
    result.reverse()
    print(*result)

방식은 간단하다. 나눠지고, 해당 값이 최초로 방문했을때에만 new_stack에 넣어주고,

그때의 위치정보를 dictionary에 저장시켜준다.

그리고 1에 도착하면 역으로 추적해가면서 최초의 숫자가 나올때까지 반복을 해주면 되는 문제이다.

import sys
import heapq
input = sys.stdin.readline

N = int(input())
heap = []
init_list = [list(map(int,input().split())) for _ in range(N)]

init_list.sort()
result = [0 for _ in range(100001)]
INF = float('inf')
for start_time,end_time in init_list:
    if heap:
        if heap[0] <= start_time:
            heapq.heappop(heap)
        heapq.heappush(heap,end_time)
    else:
        heapq.heappush(heap,end_time)
total_cnt = len(heap)
print(total_cnt)

check_number = []
min_chair_number = []
for start_time,end_time in init_list:
    if check_number:
        while check_number and check_number[0][0] <= start_time:
            _,pop_idx = heapq.heappop(check_number)
            heapq.heappush(min_chair_number,pop_idx)
        if not min_chair_number:
            idx = len(check_number)
            heapq.heappush(check_number,(end_time,idx))
            result[idx] += 1
        else:
            idx = heapq.heappop(min_chair_number)
            heapq.heappush(check_number,(end_time,idx))
            result[idx] += 1
    else:
        result[0] += 1
        heapq.heappush(check_number,(end_time,0))
print(*result[:total_cnt])

첫번째 풀이는 다음과 같다.

먼저 전체 컴퓨터의 개수를 구해준다.

check_number에는 끝시간과 사용하고 있는 사람이 있는 컴퓨터의 index를 넣어준다.

그리고 시작시간보다. 끝나는시간이 먼저 끝났을때에는 그걸 min_chair_number에 빈 컴퓨터의 index를 넣어준다.

만약 이미 들어차있는 check_number에 현재 시작시간보다 작은것이 하나도 없다하면,

먼저 min_chair_number가 있으면 min_chair_number에서 빈자리를 꺼내서 check_number에 넣어준다.

그리고 min_chair_number가 없으면 현재 주어진 컴퓨터에서 전부 자리가 꽉찬거이므로, 새 컴퓨터를 발급해주고,

그 값을 check_number에 넣어주면 된다.

import sys
import heapq
input = sys.stdin.readline
N = int(input())
time_list = []
for i in range(N):
    start_time,end_time = map(int,input().split())
    heapq.heappush(time_list,(start_time,i))
    heapq.heappush(time_list,(end_time,i))
isSeatperson = [-1]*N
seat_info = []
com_idx = 0
min_com_list = []

while time_list:
    _,person_number = heapq.heappop(time_list)

    if isSeatperson[person_number] == -1:
        if min_com_list:
            isSeatperson[person_number] = heapq.heappop(min_com_list)
        else:
            isSeatperson[person_number] = com_idx
            com_idx += 1
    else:
        heapq.heappush(min_com_list,isSeatperson[person_number])
        seat_info.append(isSeatperson[person_number])


max_com = max(seat_info)+1

result = [0]*max_com

for com_number in seat_info:
    result[com_number] += 1

print(max_com)
print(*result)

좀 더 깔끔한 풀이는 다음과 같다.

시작시간과 끝시간을 두개로 나눠서 time_list에 넣어준다.

그리고 난뒤에 하나씩 꺼내주면서, 만약에 이 사람이 앉을때 즉 start_time일때에는 min_com_list에 남은게 있으면,

하나를 출력해서 배정을 시켜준다.

그리고 그게 아니면 새로운 컴을 발급시켜주고, 그때의 idx를 증가시켜준다.

그리고 퇴실할때 나간 사람의 자리를 넣어준다.

그리고 마지막으로 그 사람이 앉았던 자리 정보를 seat_info에 저장시켜준다.

이렇게 전체 자리수를 구하고, seat_info를 통해 각 자리마다 앉았던 사람들의 정보를 저장시켜준다.

import heapq
import sys
input = sys.stdin.readline
def find_parents(X):
    if make_set[X] ==X:
        return X
    else:
        make_set[X] = find_parents(make_set[X])
        return make_set[X]


def union(a,b):
    X = find_parents(a)
    Y = find_parents(b)
    if X == Y:
        return False
    if rank[X]< rank[Y]:
        X,Y = Y,X
    make_set[Y] = X
    if rank[X] == rank[Y]:
        rank[X] += 1
    return True


P,W = map(int,input().split())

c,v = map(int,input().split())

weight_list = [list(map(int,input().split())) for _ in range(W)]
make_set = [i for i in range(P)]
weight_list.sort(key=lambda x : x[2])
rank = [1 for _ in range(P)]
result = float('inf')
while find_parents(c) != find_parents(v):
    node_a,node_b,pay = weight_list.pop()
    if union(node_a,node_b):
        result = pay


print(result)

  이 문제를 푸는 방식은 다음과 같다. 최대 길이를 구하고, 그때의 최소 너비를 구하면 되는 것이다.

그러므로 크루스칼 알고리즘대로 푸는 대신 가장 앞에서부터 pop을 하던것에서 가장 뒤에서부터 pop을 하면서

그 두 노드가 같은 집합이 아닐때 합쳐주면서 그때의 pay를 result에 저장해주면 되는 방식으로 풀면 된다.

import sys
import heapq


input = sys.stdin.readline

P,W = map(int,input().split())

start_city,end_city = map(int,input().split())

graph = [{} for i in range(P)]

for _ in range(W):
    x,y,pay = map(int,input().split())
    graph[x][y] = max(graph[x].get(y,0),pay)
    graph[y][x] = max(graph[y].get(x,0),pay)


max_width_list = [0]*P
max_width_list[start_city] = float('inf')

node_list = []

heapq.heappush(node_list,(-float('inf'),start_city))


while node_list:
    maximun_width,cur_node  = heapq.heappop(node_list)
    maximun_width = -maximun_width
    for next_node in graph[cur_node]:
        
        cur_maximun_width = min(graph[cur_node][next_node],maximun_width)

        if cur_maximun_width > max_width_list[next_node]:
            max_width_list[next_node] = cur_maximun_width
            heapq.heappush(node_list,(-max_width_list[next_node],next_node))


print(max_width_list[end_city])

프림 알고리즘으로 푸는 방식은 거의 동일하다. 대신 cur_maximun_width가 다른데, 현재의 간선의 너비와 지금까지 최대 간선의 너비와 비교해서

그 중 더 큰 값을 비교에 쓴다.

이 점만 주의하고, 최소힙이 아니라 최대힙을 사용하면 해당 문제를 풀 수 있다.

이 문제는 데이터 수정이 있기 전까지 안 풀기 를 권장합니다.

이 문제를 푸실분들은 https://www.acmicpc.net/board/view/69371 이 글을 참조하거나

밑의 input을 받는 방식으로 받기를 권장합니다.

import sys
from itertools import product
def input():
    return sys.stdin.readline().rstrip()

def dfs(first_num,idx,total):
    global result
    if idx == line_cnt[1]:
        str_total = str(total)
        str_set = set(str_total)
        if len(str_total) == line_cnt[idx+2] and not (str_set-total_num):
            result += 1
    else:
        for k in int_total_num:
            temp = k*first_num
            str_temp = str(temp)
            str_set = set(str_temp)
            if len(str_temp) == line_cnt[idx+2] and not (str_set-total_num):
                number_of_digit = 10**idx
                temp_num = temp * number_of_digit
                dfs(first_num,idx+1,total+temp_num)


N = int(input())
list_ = input().split()

K = input()
list__ = input().split()

if len(K) == 0:
    K = int(list_[N])
    list__ = list_[N + 1 : ]
    list_  = list_[ : N]
else:
    K = int(K)
line_cnt = list(map(int,list_))
number_list = list__[:]
total_num = set(number_list)
int_total_num = set(map(int,number_list))
result = 0
for num_line1 in product(number_list,repeat=line_cnt[0]):
    first_line_num = int(''.join(num_line1))
    dfs(first_line_num,0,0)


print(result)

이 문제의 아이디어 자체는 그리 어렵지 않다.

모든 것을 다 구해보면 된다.

하다가, 안되는 경우가 발생하면 되돌아가서 새로운 걸 하면 된다.

저같은 경우엔 첫줄의 숫자는 product를 이용해 구했다.

그리고 두번째 숫자부터는 직접 중복순열을 해주면서, 중간에 모든 조건을 만족해야지만, 그 다음 조건으로 갈 수 있게 해주었다.

그리고 주어진 숫자가 있는지 없는지는 차집합을 통해 길이가 0이면 전부 있는것이므로, 길이가 0인경우에만 통과시켜줬다.

import sys


def input():
    return sys.stdin.readline().rstrip()

def choose_1(idx,val):
    global K
    if idx == line_cnt[0]:
        choose_2(0,0,val)
        return
    else:
        for i in range(K):
            choose_1(idx+1,val*10+number_list[i])
def check_length(val):
    val = str(val)
    return len(val)
def check_number(val):
    while val:
        if not number_visit[val%10]:
            return False
        val = val//10
    return True

def choose_2(idx,val,first_num):
    global K,result
    if idx == line_cnt[1]:
        last_num = first_num * val
        if check_length(last_num) == line_cnt[-1] and check_number(last_num):
            result += 1
        return
    else:
        for i in range(K):
            if check_length(first_num*number_list[i]) == line_cnt[idx+2] and check_number(first_num*number_list[i]):
                choose_2(idx+1,val*10+number_list[i],first_num)

N = int(input())
list_ = input().split()

K = input()
list__ = input().split()

if len(K) == 0:
    K = int(list_[N])
    list__ = list_[N + 1 : ]
    list_  = list_[ : N]
else:
    K = int(K)
result = 0
line_cnt = list(map(int,list_))
number_list = list(map(int,list__))
number_visit = [False for _ in range(10)]

for num in number_list:
    number_visit[num] = True


choose_1(0,0)

print(result)

이 방식은 좀 더 깔끔한 방식인것같다.

여기는 나머지를 이용해서 각 자리수를 구하고, 그때 숫자가 있는지 없는지는 리스트의 방문표시로 해주었다.

길이는 문자열로 바꾼뒤 그 길이를 구해주었다.

이 방식이 좀 더 깔끔한 코드라 생각한다.

import sys
from collections import deque,defaultdict
input = sys.stdin.readline
# 강의 근원 노드의 순서는 1이다.

T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    # K case의 번호
    # M은 노드의 수
    # P는 간선의 수

    strahelr_dict = [defaultdict(int) for _ in range(M+1)]
    strahelr_list = [-1 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]
    indegree_list = [0 for _ in range(M+1)]
    for _ in range(P):
        x,y = map(int,input().split())
        graph[x].append(y)
        indegree_list[y] += 1
    stack = deque()
    for i in range(1,M+1):
        if not indegree_list[i]:
            stack.append(i)
            strahelr_list[i] = 1
    
    while stack:

        node = stack.popleft()
        cur_strahler = strahelr_list[node]
        for next_node in graph[node]:
            indegree_list[next_node] -= 1
            strahelr_dict[next_node][cur_strahler] += 1
            if not indegree_list[next_node]:
                stack.append(next_node)
                next_strahelr = max(strahelr_dict[next_node].keys())
                if strahelr_dict[next_node][next_strahelr] > 1:
                    strahelr_list[next_node] = next_strahelr + 1
                else:
                    strahelr_list[next_node] = next_strahelr



    print(K,strahelr_list[M])

 이 문제에서 주의해야할 점은,  마지막에 출력해야할 TEST CASE의 값이 T가 아니라, K인걸 주의해야한다.

처음은 위상정렬을 해주는 것과 동일하게 indegree와 graph를 그려준다.

가장 처음에 출발하는 node들의 strahler의 값을 1로 초기화를 해준다.

위상정렬을 해주면서, 방문하는 노드들에 해당 cur_strahler의 개수를 세줍니다.

그러면서 indegree가 0이 되었을때, 최대값을 찾고, 그 개수가 2개 이상이면, 최대값보다 1을 더해서 저장시켜줬습니다.

위와 같이 한뒤에 나머지는 일반적인 위상정렬을 구하면 되는 문제였습니다.

# 42_jakang님 풀이
import sys
input = sys.stdin.readline


def tree_dp(cur_node):

    if not len(graph[cur_node]):
        strahler_list[cur_node] = 1
        return
    else:
        max_st_cnt = 0
        for parent_node in graph[cur_node]:
            tree_dp(parent_node)

            if strahler_list[cur_node] < strahler_list[parent_node]:
                strahler_list[cur_node] = strahler_list[parent_node]
                max_st_cnt = 1
            elif strahler_list[cur_node] == strahler_list[parent_node]:
                max_st_cnt += 1
        if max_st_cnt > 1:
            strahler_list[cur_node] += 1
T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    strahler_list = [0 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]

    for _ in range(P):
        x,y = map(int,input().split())
        graph[y].append(x)

    

    tree_dp(M)
    print(K,strahler_list[M])
    

 이 풀이는 42_jakang님의 풀이를 공부하면서 한것이었고, 이 풀이 방식은 다음과 같습니다.

어차피 가장 끝노드 M은 고정되어있으므로, 가장 끝 노드에서부터 하나하나씩 부모를 찾아 들어가봅니다.

그리고 부모노드의 strahler_list가 현재노드보다 크면 갱신을 해주고, 그 큰값들의 개수를 세줍니다.

만약에 그 개수가 2개 이상이면, 현재노드의 shrahler의 값을 키워줍니다.

이런 방식을 이용해서도 문제를 풀 수 있습니다.

import sys

input = sys.stdin.readline


while True:
    N,*arr = list(map(int,input().split()))

    if N == 0:
        break

    stack = [0]
    arr = [0] + arr[:] +[0]
    result = 0
    for ind in range(1,len(arr)):
        while stack and arr[ind] < arr[stack[-1]]:
            height = arr[stack[-1]]
            stack.pop()
            width = ind - stack[-1]-1
            result = max(result,height*width)
        stack.append(ind)

    print(result)

 이 문제는 boj.kr/11873 의 하위호환이다.

11873의 문제를 푼것과 같이 stack에 현재위 index 즉 가로길이를 넣어주는 걸 한다.

그리고 이걸 좀 더 쉽게 구하기 위해, 양 끝에 [0]을 추가를 해준다.

그러면 스택에서 마지막 값에 위치한 높이보다 작은 높이가 들어오면,

그때 스택에서 값을 추출해서, 지금까지의 거리를 측정을 해준다.

측정 방식은 현재 index에서 stack의 마지막값을 빼준 값에 -1을 해준것이다.

이렇게 2개의 값을 곱한뒤 최대값을 저장해주면 된다. 

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())


for tc in range(T):
    N = int(input())
    graph = [[0 for _ in range(N+1)] for _ in range(N+1)]
    # 전년도 1등부터 ~ N등까지 팀 순서
    prev_order_team = list(map(int,input().split()))
    indegree = [0]*(N+1)
    indegree[0] = float('inf')
    for rank,team_num in enumerate(prev_order_team):
        indegree[team_num] = rank
        for low_team_num in prev_order_team[rank+1:]:
            graph[team_num][low_team_num] = 1

    M = int(input())
    new_indegree = indegree[:]
    for _ in range(M):
        a_team,b_team = map(int,input().split())
        if indegree[a_team] > indegree[b_team]:
            a_team,b_team = b_team,a_team

        # a_team이 상위권 b_team이 하위권 원래는
        graph[b_team][a_team] = 1
        graph[a_team][b_team] = 0
        new_indegree[a_team] += 1
        new_indegree[b_team] -= 1
    indegree = new_indegree[:]
    stack = deque()

    for team_num in range(1,N+1):
        if not indegree[team_num]:
            stack.append(team_num)
    result = []
    if len(stack) == 1:
        cnt = 0
        while cnt<N:
            if not len(stack):
                result = 'IMPOSSIBLE'
                break
            elif len(stack) > 1:
                result = '?'
                break

            cur_node = stack.popleft()
            result.append(cur_node)
            for next_node in range(1,N+1):
                if graph[cur_node][next_node]:
                    indegree[next_node] -= 1
                    if not indegree[next_node]:
                        stack.append(next_node)
            cnt += 1
    elif len(stack) == 0:
        result = 'IMPOSSIBLE'
    else:
        result = '?'
    if type(result) == list:
        print(*result)
    else:
        print(result)

이 문제는 최근에 풀었던 문제 중에서 문제를 이해하는데 가장 힘들었던 문제였다. 문제를 이해하고 보면,

쉽게 이해가 가능한 문제이다.

문제에 주어진 N개의 숫자는

앞에서부터 1등부터 N등까지를 표현한 것이다.

그리고 그 각 자리에 있는것이 1등을 한 팀 N_1  2등을 한 팀 N_2 이런식인것이다.

그러면 문제에 첫 예제로 주어진

5 4 3 2 1

1등은 5팀

2등은 4팀

3등은 3팀

4등은 2팀

5등은 1팀

이 된것이다. 그렇다는 것은 이걸 그래프적으로 표현을 하면 다음과 같다.

 다음 과 같이 표현을 할 수 있을 것이다.

5팀이 가장 루트 노드이고, 이 5팀을 지나가고 난뒤에 4팀 3팀 2팀 1팀을 순서적으로 할 수 있는것이다.

그러면 여기서 상대적인 등수가 바뀌었다는 것은

저 그래프에서의 순서가 뒤바뀐다는 것을 의미하게 된다.

그러면 첫번째 예제에선

2 4

3 4 라는 입력이 주어졌다.

그러면

빨갛게 동그라미 모양이 된 화살표가 반대로 가게 되는것이다.

즉 녹색화살표 처럼 반대로 표시가 바뀌게 된것이다.

그러면 이때의 순위는

5 -> 3->2->4->1 순서가 되는 것을 알 수 있다.

그래서 이 문제에서 중요한 것은

처음 입력이 주어졌을때 자기 등수보다 이하의 등수들에게 부모 자식 관계를 나타내느 그래프 간선을 그려준다.

그리고 난뒤에 m개의 상대적인 순위가 바뀌었다는 입력이 들어오면

서로원래의 rank를 확인해서

높은 랭크 -> 낮은 랭크로 연결되어있던 간선을 반대로 바꾸어주고,

우리가 간선을 들어온 개수를 세어놓은 indegree 수치를

낮은 순위는 1개를 줄여주고, 높은 순위는 1개를 높여주면 된다.

그리고 여기서 주의해야할 것은 바로 값을 바꾸면 바뀐 순위를 참조가 가능하므로,

복사된 배열에서 값을 변경시키고 나중에 옮겨줘야한다.

그리고 정상적인 위상정렬을 시행해주면 된다.

만약에 스택이 비게되면 사이클이 발생한 것이므로,  impossible을

스택에 길이가 2개이상이 된다는것은 같은 rank에 2개가 있게 되는 것이므로, ?를 출력하게 해주면 된다.

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())

    prev_rank = [0]*(N+1)
    current_rank = [0]*(N+1)
    arr = list(map(int,input().split()))
    for i in range(N):
        prev_rank[arr[i]] = i +1
        current_rank[arr[i]] = i + 1

    M = int(input())

    for _ in range(M):
        a_team,b_team = map(int,input().split())

        if prev_rank[a_team] > prev_rank[b_team]:
            current_rank[a_team] -= 1
            current_rank[b_team] += 1
        else:
            current_rank[a_team] += 1
            current_rank[b_team] -= 1

    result = [0]*(N+1)
    flag= False
    for team_num in range(1,N+1):
        if result[current_rank[team_num]]:
            flag = True
            break
        else:
            result[current_rank[team_num]] = team_num

    if flag:
        print('IMPOSSIBLE')
    else:
        print(*result[1:])

 이건 좀 더 간단한 풀이이다.

 하지만 이 풀이는 ?인 경우가 없다고 가정하고 푼 것이다.

N,K = map(int,input().split())
N += 1
N_list = list(str(N))
cur_idx = -1
max_idx = len(N_list)
while True:
    if N_list.count('5') >= K:
        break
    while N_list[cur_idx] == '5' and abs(cur_idx) < max_idx:
        cur_idx -= 1
    
    cur_value = int(''.join(N_list))
    cur_value = cur_value + 10**(abs(cur_idx)-1)
    N_list = list(str(cur_value))
    max_idx = len(N_list)



print(''.join(N_list))

이 문제는 간단하다. 가장 뒤에서부터 5를 만들어주면 되는것이다. 

여기서 주의해야할 점은 다음과 같은 경우이다. K가 1이고, 주어진 N이 48이였을때

우리는 49부터 탐색을 시작하게 되는데, 그때 50이 되면 K를 만족하는 수가 된다.

그러므로 우리는 5가 아닌 자리수부터 1씩 늘려가면서, 가장 오른쪽 자리부터 5를 만들어줘야한다.

그래서 나는 cur_idx 라는것을 뒤에서부터 접근하기 위해 -1로 해주었고, 

abs(cur_idx) - 1을 해주면 해당 자릿수를 구할 수 있다. 즉 첫번째 자리는 1이 더해지게, 오른쪽에서 두번째자리는 10,

세번째 자리는 100이 더해지게 만들어주는 것이다.

이럴때 주의해야할 점은 999일때이다. 999에서 1을 더해주면 1000이된다. 그러면 우리의 idx가 넘어가게 되므로,

max_idx를 새로 계속 갱신을 해주었다.

그리고 555 이고, 구하는 K가 4일때를 대비해서 while문에 abs(cur_idx)<max_idx 를 넘어갈때를 escape 해주었다.

이런식으로 오른쪽 자리수부터 1씩 더해가면서 5를 만들어주고, 그리고 count를 해서 넘어가면

반복문을 빠져 나올 수 있게 해주었다.

여담으로 문제 제목이 직관적이고, 가장 짧은 문제였던 것 같다.