Coding 공부

import heapq
import sys
input = sys.stdin.readline

T,N = map(int,input().split())

heap_list = []


for _ in range(N):
    id_num,times,C = map(int,input().split())
    heapq.heappush(heap_list,(-C,id_num,times))

result = []
for _ in range(T):

    prioty,id_num,times = heapq.heappop(heap_list)
    times -= 1
    result.append(id_num)
    if times != 0:
        heapq.heappush(heap_list,(prioty+1,id_num,times))


for i in range(T):
    sys.stdout.write(str(result[i])+'\n')

시간초과에 많이 힘들었던 문제였다. 문제를 푸는 로직은 맞지만, 출력을 하는데 시간이 오래 걸리는것 같다.

이 문제의 주어진 조건은 한 타임에 실행된 프로세스를 제외한, 나머지 프로세스들의 우선순위가 전부 1이 증가한다.

이 말의 뜻은 자기만 우선순위가 1이 줄어드는것과 같다.

그러므로 이 문제는 heapq를 이용해서 1순위로 priority가 가장 높은게 가장 앞으로 오게, 그 다음은 id가 가장 작은게 오도록 넣어준다.

그리고 하나씩 꺼내면서 시간을 줄여주고, 우선순위도 줄여주는데 max_heapq를 해야하므로, 여기서는 +1을 해주었다.

만약 시간이 0 이면 그 프로세스는 실행이 안되므로, push를 해주지 않았다.

import sys
import math
def init():
    global tree_size

    for i in range(tree_size-1,0,-1):
        segement_tree[i] = segement_tree[i*2] + segement_tree[i*2+1]


def update(index,diff):
    while index >= 1:
        segement_tree[index] += diff
        index//=2

def sum_range(node_number,start,end,left,right):
    if left > end or start > right:
        return 0
    if (left <= start) and (end <= right):
        return segement_tree[node_number]
    return sum_range(node_number*2,start,(start+end)//2,left,right) + sum_range(node_number*2+1,(start+end)//2+1,end,left,right)
input = sys.stdin.readline

N,M = map(int,input().split())

height = math.ceil(math.log2(N))
tree_size = 2**height
total_size = 2**(height+1)

segement_tree = [0]*total_size

for i in range(N):
    segement_tree[tree_size + i] = 0
init()
for i in range(M):
    command = list(map(int,input().split()))
    if command[0] == 1:
        diff = command[2] - segement_tree[tree_size + command[1] - 1]
        update(command[1]+tree_size-1,diff)
    else:
        if command[1] > command[2]:
            command[1],command[2] = command[2],command[1]
        print(sum_range(1,0,tree_size-1,command[1]-1,command[2]-1))

세그먼트 트리를 이용해서 풀어야했던 문제이다.

여전히 세그먼트 트리는 정확히 잘 모르겠다는게 함정이지만, 예전에 만들어뒀던 세그먼트 트리에서 일부분만 고쳤다.

구간의 값을 특정위치에 미리 저장을 해놓고, 어떤 위치의 값이 변했을때, 그 값이 포함된 구간들을 갱신하는 것인데,

아직 세그먼트 트리는 어려운 것같다.

세그먼트 트리를 짜놓은 코드를 이용해서, 풀라면 풀수 있을것 같지만, 실전에서 노베이스부터 설계를 하라고 하면

너무 어려울 것 같다.

import sys

input = sys.stdin.readline


def init(N):
    for i in range(N-1,0,-1):
        tree[i] = tree[i<<1] + tree[i<<1|1]

def query(left,right,N):
    ans = 0
    left = left +N
    right = right +N
    while left<right:
        if (left&1):
            ans += tree[left]
            left += 1
        if (right&1):
            right -= 1
            ans += tree[right]
        
        left >>= 1
        right>>= 1
    return ans


def update(pos,val,N):
    tree[pos+N] = val
    pos = pos +N
    while pos > 1:
        tree[pos>>1] = tree[pos] + tree[pos^1]
        pos >>= 1
N,M = map(int,input().split())


tree = [0]*(3*N)


for _ in range(M):
    command = list(map(int,input().split()))
    if command[0] == 1:
        update(command[1],command[2],N)
    else:
        if command[1] > command[2]:
            command[1],command[2] = command[2],command[1]

        sys.stdout.write(str(query(command[1],command[2]+1,N))+'\n')

 이 코드는 https://blog.joonas.io/129 에 있는 비재귀 세그먼트 트리를 설명한 글을 이용해서 푼 문제이다.

여전히 어렵다. 

업데이트가 빈번하고, 특정값을 구할때, 트리를 이용한 풀이들이 많은데, 아직 트리에 대해 정확히 알지 못해서

그런지 많이 어렵다.

import sys
input = sys.stdin.readline


G = int(input())
P = int(input())
result = 0
plane = [int(input()) for _ in range(P)]


parents_number = [i for i in range(G+1)]

visited = [False]*(G+1)
cur_idx = 0
planing = True

while cur_idx<P and planing:

    cur_plane_number = plane[cur_idx]
    check = [cur_plane_number]
    while visited[cur_plane_number] and cur_plane_number>0:
        cur_plane_number = parents_number[cur_plane_number]
        check.append(cur_plane_number)
    
    
    
    if cur_plane_number == 0:
        break
    else:
        visited[cur_plane_number] = True
        for num in check:
            parents_number[num] = cur_plane_number-1

    cur_idx += 1

print(cur_idx)

이 문제는 프로그래머스의 호텔 방 배정하기하고 동일한 문제라고 볼수 있다.

주어진 위치가 있고, 1~위치 사이에 비행기를 도킹할 수 없으면, 멈추면 되는것이다.

호텔 방 배정하기하고 동일하게, 자신의 다음 도킹 위치를 저장시켜놓으면 된다. 

그러면서 최악의 경우를 방지하기 위해, 그 다음 도킹위치를 새로 갱신해주는 작업을 해주면 된다.

import sys

input = sys.stdin.readline

def find_parent(idx):
    if idx == make_set[idx]:
        return idx
    else:
        make_set[idx] = find_parent(make_set[idx])
        return make_set[idx]

G = int(input())
P = int(input())

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


result = 0
for k in range(P):
    plane_num = int(input())
    gate_num = find_parent(plane_num)

    if gate_num < 1:
        break
    else:
        make_set[gate_num] = make_set[gate_num-1]
        result += 1
        

print(result)

이거는 좀 더 함수로 만들어놓은 것이다.

위와 똑같은 로직이지만, find_parent 라는 재귀함수를 통해, 자동적으로 갱신이 되게 해주었다.

호텔 방 배정하기 문제를 수월하게 풀었으면 이 문제도 수월하게 풀 수 있을거라 생각한다.

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

def union(x,y):
    X = find_parent(x)
    Y = find_parent(y)
    if X == Y:
        return 0

    else:
        if child_cnt[X]< child_cnt[Y]:
            make_set[X] = Y
            return_value = child_cnt[X] * child_cnt[Y]
            child_cnt[Y] += child_cnt[X]
        else:
            make_set[Y] = X
            return_value = child_cnt[X] * child_cnt[Y]
            child_cnt[X] += child_cnt[Y]

        return return_value
            
        

N,M,Q = map(int,input().split())


graph = [{} for i in range(N+1)]

make_set = [i for i in range(N+1)]
child_cnt = [1 for i in range(N+1)]
connect_input = [[],]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x][y] = 1
    graph[y][x] = 1
    connect_input.append((x,y))

result = 0
disconnet_list = []

for _ in range(Q):
    ind = int(input())
    x,y = connect_input[ind]
    graph[x][y] = 0
    graph[y][x] = 0
    disconnet_list.append(ind)


for i in range(1,M+1):
    if i not in disconnet_list:
        x,y = connect_input[i]
        union(x,y)


while disconnet_list:
    ind = disconnet_list.pop()
    x,y = connect_input[ind]
    result += union(x,y)
print(result)

이 문제는 역으로 생각하는 편이 제대로 푸는 방식이었다 윗 코드는 첫 풀이이다.

문제를 푸는 방식은 다음과 같다. 문제에서 주어진 끊어진 조건들을 전부 끊어졌다고 가정을 하고

끝에서부터 하나씩 연결을 해가면서 반대로 추적을 하는것이다.

그러므로, 먼저 전체 연결리스트를 들어온 순서에 맞게 index에 알맞게 저장을 해준다.

그리고 난뒤에 끊어진 목록들을 따로 저장을 해두고, 끊어지지 않은 연결들끼리 서로 union find를 해준다.

union_find를 하면서, 각자의 노드 개수를 저장해주는 리스트를 따로 만들어두고,

서로 다른 집합이 합쳐질때 그 두 개의 노드의 개수를 합쳐주는 로직을 해주면 된다.

이렇게 연결이 된 간선들로 union find를 1차적으로 진행을 한다.

그리고 끝에서부터 끊어진 간선들끼리 연결을 해준다. 그러면 그 간선을 끊기전 모습으로 돌아갈 수 있다.

이렇게 하면서 서로의 집합이 같으면 0을 반환하고, 그게 아니면 서로의 집합의 개수를 곱한 수를 반환하도록 했다.

import sys

input = sys.stdin.readline


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

def union(x,y):
    X = find_parent(x)
    Y = find_parent(y)
    if X == Y:
        return 0

    else:
        if rank[X] < rank[Y]:
            X,Y = Y,X

        size_a,size_b = rank[X],rank[Y]
        rank[X] += rank[Y]
        make_set[Y] = X
        return size_a*size_b
            
        

N,M,Q = map(int,input().split())



make_set = [i for i in range(N+1)]
rank = [1 for _ in range(N+1)]
connect_input = [[],]
check = [True]*(M+1)
for _ in range(M):
    x,y = map(int,input().split())
    connect_input.append((x,y))

result = 0
disconnet_list = []

for _ in range(Q):
    ind = int(input())
    disconnet_list.append(ind)
    check[ind] = False


for i in range(1,M+1):
    if check[i]:
        x,y = connect_input[i]
        union(x,y)


while disconnet_list:
    ind = disconnet_list.pop()
    x,y = connect_input[ind]
    result += union(x,y)
print(result)

좀 더 깔끔하고 빠른 풀이 방식이다. 첫 풀이 코드같은경우엔 느렸는데

그 이유는 간선이 연결됬는지 안됬는지를 구분하는데 not in 으로 했기 때문에, O(N)의 시간이 걸려서 느려진 문제가 있었다.

그래서 간선들이 연결이 됬는지 안됬는지를 구분하는 리스트를 만들어두고 바로 확인이 가능하도록 했다.

https://www.secmem.org/blog/2021/03/21/Disjoint-Set-Union-find/

설명은 잘 못하므로 위의 링크에 있는 Union_find를 보면 알겠지만, rank compression을 활용해서 시간을 좀 더 줄였다.

Union find는 크루스칼알고리즘에서 처음으로 알게 되었는데, 크루스칼에서만 쓰이는줄 알았는데,

생각외로 단독으로 쓰이는 곳이 많았다. 이걸 짜는데 어색해서 크루스칼 알고리즘을 잘 안쓰는데,

좀 더 숙달되도록 노력해야겠다.

arr = list(input())
N = len(arr)
left_bracket = 0
right_bracket = 0
total_bracket = 0
result = 0
for i in range(N):
    if arr[i] == '(':
        left_bracket += 1
        total_bracket += 1
    else:
        right_bracket += 1
        total_bracket -= 1

    if total_bracket <= 1:
        left_bracket = 0

    if total_bracket == -1:
        result = right_bracket
        break


if total_bracket > 0:
    result = left_bracket

print(result)

이 문제는 어려웠던 문제였다. 이 문제는 괄호의 특성을 이해하고, 그것의 패턴을 찾아서 생각을 해줘야했던 문제였다.

이 문제의 조건은 최대 1개의 오타가 존재할 수 있다.

여는 괄호를 +1, 닫는 괄호를 -1로 할씨, 마지막의 최종 괄호의 수가 -2 이거나 2이면 1개의 오타가 존재하는 것이고,

-1이 되는 순간 닫는괄호가 1개가 더 많은 것을 확인할수 있는 순간이다.

이 문제에서 닫는괄호의 갯수가 더 많을 경우에는 닫는 괄호가 더 많아지는 그 순간에서의 닫는 괄호의 갯수만큼을 바꿀수 있다.

그리고, 이 문제에서 어려웠던 것은 왼쪽괄호가 더 많을 경우이다. 왼쪽 괄호가 더 많은 경우에는 왼쪽괄호가 절대 바뀔수 없는 경우들을 생각을 해줘야한다.

만약 여는 괄호의 수가 닫는괄호의 수보다 2개이상 많지 않으면, 그 괄호들은 바꿀수가 없다. 이 문제에서 최외각의 괄호들은 왼쪽은 여는괄호 오른쪽은 닫는괄호 인 것을 상기해보면 풀 수 있다.

이러한 점을 응용해, 전체 브라켓의 갯수가 1개 이하일때에는 왼쪽 괄호의 수를 계속 0으로 초기화를 시켜주는 작업을 하고, 그 이후부터 잉여 왼쪽 브라켓의 개수를 세주는 작업을 하는 방식으로 풀 수 있다.

# 	babygranfa 코드 분석
arr = list(input())
N = len(arr)
left_bracket = 0
right_bracket = 0
total_sum = 0
left_stack = []
right_stack = []
left_list = [0]*N
right_list = [0]*N

for i in range(N):
    if arr[i] == '(':
        left_bracket += 1
        total_sum += 1
        left_stack.append(i)
    else:
        right_bracket += 1
        total_sum -= 1
        if left_stack:
            left_stack.pop()
        else:
            right_stack.append(i)
    
    left_list[i] = left_bracket
    right_list[i] = right_bracket

if total_sum > 0:
    print(left_list[-1] - left_list[left_stack[-1]]+1)
elif total_sum <0:
    print(right_list[right_stack[0]])
else:
    print(0)

이 방식은 다른사람의 풀이를 보고 습득한 방법이다.

이 풀이는 자료구조를 이용해서, 여는 괄호의 위치를 저장해주는 스택과 닫는 괄호를 저장해주는 스택을 해준다.

여기서 쌍을 이루는 스택들은 하나씩 제거를 해주면서, 여는 괄호가 없고, 닫는괄호가 있을때에는 그때의 위치를 저장시켜준다.

이런식으로 하면서, 전체 브라켓의 개수가 양수일때에는 왼쪽괄호가 더 많은 것이므로, 왼쪽괄호의 최종 개수에서 마지막 왼쪽괄호의 스택이 위치가 존재하는 곳의 왼쪽괄호의 개수를 빼주고 1개를 더해준다. 그 위치의 왼쪽괄호도 포함되어야하기 때문이다.

그리고 오른쪽괄호같은경우엔, 최초로 오른쪽괄호가 많아지는 곳의 오른쪽괄호의 수를 출력해주면 된다.

이 문제는 괄호의 특성을 이해하고, 그것을 적용시키는 문제로, 저에게 상당히 어려웠던 문제였다.

import heapq
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
arr.sort()
# 끝나는 시간들을 저장해놓는 배열
end_time_list = []
for start_time,end_time in arr:
    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))

N = int(input())

metting = []
for _ in range(N):
    start,end = map(int,input().split())
    metting.append([start,1])
    metting.append([end,-1])
metting.sort()
result = 0
metting_cnt = 0 
for _,state in metting:
    metting_cnt += state
    result = max(metting_cnt,result)
print(result)

N = int(input())

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

arr.reverse()
result = [-1]
stack = [arr[0]]

idx = 1
while idx <N:
    while stack and stack[-1] <= arr[idx]:
        stack.pop()
    if stack:
        result.append(stack[-1])
    else:
        result.append(-1)
    stack.append(arr[idx])
    idx += 1
result.reverse()
print(*result)

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))
result = [-1]*N
stack = [0]
idx = 1
while stack and idx<N:
    while stack and arr[stack[-1]] < arr[idx]:
        result[stack.pop()] = arr[idx]
    stack.append(idx)
    idx += 1

print(*result)

import sys

input = sys.stdin.readline

N = int(input())

M = int(input())
S = [0]*N
E = [0]*N
for _ in range(M):
    x, y = map(lambda x : x-1 ,list(map(int,input().split())))

    S[x] += 1
    E[y] += -1




ind = 0
result = 0
big_cnt = 0
while ind<N:
    if big_cnt:
        big_cnt += S[ind] + E[ind]
        if big_cnt == 0:
            result += 1
        ind += 1
    else:
        if S[ind] == 0:
            result += 1
        else:
            big_cnt += S[ind]
        
        ind += 1
print(result)