Coding 공부

import sys
import bisect
def time_str_num(times):
    return times[:4]+times[5:7]+times[8:10]+times[11:13]+times[14:16]+times[17:19]

input = sys.stdin.readline

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

lev_list = [[] for _ in range(7)]
for _ in range(N):
    times,lev = input().split('#')
    times = time_str_num(times)
    lev_list[int(lev)].append(times)

result = []

for _ in range(Q):
    s_time,e_time,lev = input().split('#')

    s_time = time_str_num(s_time)
    e_time = time_str_num(e_time)
    lev = int(lev)
    cnt = 0
    for cu_lev in range(lev,7):
        s_ind = bisect.bisect_left(lev_list[cu_lev],s_time)
        e_ind = bisect.bisect_right(lev_list[cu_lev],e_time)
        cnt += (e_ind-s_ind)

    result.append(cnt)


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

대회때 시간초과가 났던 문제다.

이 문제는 https://programmers.co.kr/learn/courses/30/lessons/17676 와 https://programmers.co.kr/learn/courses/30/lessons/72414 에서 비슷한 느낌을 받았던 문제이다.

이 2문제 전부 긴 시간대를 주고 문제에 주어진 것에서 최대값을 찾던가, 시간내에 있는 기록등을 찾는 방식이다.

이 문제 또한, 각종 로그들이 특정시간대에 나고, 시작시간과 종료시간 내에 발생한 로그의 개수를 세는 것이다.

푸는 방식은 다음과 같다. 레벨별로 시간을 나눠서 저장을 하는것이다.

어차피 들어오는 로그는 순서대로 들어오기 때문에, 작은순서대로 정렬되어서 들어가진다.

또한 년월일시분초를 다 합쳐서 14글자의 숫자로 저장해주면, 문자열로 저장해놔도, 대소구분이 되기 때문에 괜찮다.

그러면 문제에 주어진 로그들을 맞는 레벨에 하나씩 추가를 해준다.

그리고 로그가 들어오면 시작시간과 끝시간을 분리를 해놓는다.

그리고 이분탐색을 통해, 시작시간은 이 시간이 들어가야할 최소 위치,

끝시간은 이 시간이 들어갈수 있는 최대 위치를 구해준다.

위와 같은 리스트가 있다고 하고,

시작시간은 3이고, 끝시간은 4라 한다면,

시작시간은 2번인덱스을 가리켜야하고, 끝시간은 8번 인덱스를 가리켜야한다.

그러면, 8-2 = 6개가 나오는 걸 볼 수 있다.

이걸 나는 python에서 이분탐색을 위한 라이브러리인 bisect를 이용해서 bisect_left와 bisect_right를 통해 구현을 했다.

그리고 주어진 로그의 레벨이상을 전부 구하는 것이므로, 주어진 레벨에서부터 최대레벨인 6까지 전체 탐색을 해주었다.

import sys
import bisect
def time_str_num(times):
    return times[:4]+times[5:7]+times[8:10]+times[11:13]+times[14:16]+times[17:19]

input = sys.stdin.readline

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

lev_list = [[] for _ in range(7)]
for _ in range(N):
    times,lev = input().split('#')
    times = time_str_num(times)

    for i in range(1,int(lev)+1):
        lev_list[i].append(times)

for _ in range(Q):
    s_time,e_time,lev = input().split('#')

    s_time = time_str_num(s_time)
    e_time = time_str_num(e_time)
    lev = int(lev)
    cnt = 0
    s_ind = bisect.bisect_left(lev_list[lev],s_time)
    e_ind = bisect.bisect_right(lev_list[lev],e_time)
    cnt += (e_ind-s_ind)

    sys.stdout.write(str(cnt)+'\n')

   이 풀이는 위의 풀이와 똑같지만, 반복작업을 없애준 것이다.

 처음 로그가 들어올때부터, 1레벨부터 현재 레벨까지 전부 넣어주는것이다.

어차피 레벨 이상의 쿼리를 전부 조회하는 것이므로, 로그로 들어온 레벨 이하에 전부 저장을 해주고,

이분 탐색을 한번만 해서 출력할 수 있도록 해준 것이다.

대회시간에는 못 풀었지만 류호석님의 조언을 듣고 바로 풀 수 있었던 문제였다.

이전에 풀었던 문제들을 조금만 응용하면 풀수 있는 문제였지만, 제대로 응용하지 못한 패착인것 같다.

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를 해주지 않았다.

from collections import deque
import sys

R,C,T = map(int,input().split())


arr = []
start = []
for x in range(R):
    temp = list(input())

    for y in range(C):
        if temp[y] == 'G':
            start = (x,y)

    arr.append(temp)


stack = []

stack.append((*start,0,set()))
time = 0
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while time<T:
    new_stack = []
    for x,y,eat,visited in stack:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx<R and 0<=ny<C:
                if arr[nx][ny] == 'S' and (nx,ny) not in visited:
                    new_visited = set()
                    new_visited.add((nx,ny))
                    new_visited = new_visited | visited
                    new_stack.append((nx,ny,eat+1,new_visited))
                    result = max(eat+1,result)
                elif arr[nx][ny] != '#':
                    new_stack.append((nx,ny,eat,visited))
    stack = [row[:] for row in new_stack]
    time += 1

print(result)
    

대회때 풀었던 풀이는 다음과 같다 BFS를 해주면서, 모든 이동경로를 누적해줬다.

그리고 visited에 없는 경우에만 고구마를 먹도록 해줬다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def dfs(node,time,eat):
    global T,result,R,C
    if time == T:
        result = max(result,eat)
        return
    else:
        result = max(result,eat)
        for i in range(4):
            nx = node[0] + dx[i]
            ny = node[1] + dy[i]
            if 0<=nx<R and 0<=ny<C and not vistied[nx][ny]:
                vistied[nx][ny] = True
                if arr[nx][ny] == 'S':
                    dfs((nx,ny),time+1,eat+1)
                else:
                    dfs((nx,ny),time+1,eat)
                vistied[nx][ny] = False
            elif 0<=nx<R and 0<=ny<C and vistied[nx][ny] and arr[nx][ny] !='#':
                dfs((nx,ny),time+1,eat)

R,C,T = map(int,input().split())
result = 0
vistied = [[False for _ in range(C)] for _ in range(R)]


arr = []
start = []
for x in range(R):
    temp = list(input())
    for y in range(C):
        if temp[y] == '#':
            vistied[x][y] = True
        elif temp[y] == 'G':
            start = (x,y)
    arr.append(temp)


dx = [-1,1,0,0]
dy = [0,0,-1,1]

dfs(start,0,0)
print(result)

대회가 끝나고 난뒤의 풀이이다.

dfs를 해주는데 바문을 최초로 한 경우의 S일때에만 고구마를 먹도록 했다.

그리고, 방문을 했지만, 벽만 아니라면, 지나갈수 있도록 만들어줬다.

import sys

R,C = map(int,input().split())

GR,GC,PR,PC = map(int,input().split())


arr = []
P_total = PR*PC
for _ in range(R):
    temp = list(input())
    P_total-=temp.count('P')
    arr.append(temp)

if P_total:
    print(1)
else:
    print(0)

대회 때에는 너무 어렵게 생각해서 dfs,bfs를 이용해서 전체 베개의 개수를 구하는 방식으로 풀었는데,

대회 끝나고 간단한 풀이는 count로 P의 개수를 세주고, 그게 전체 배게의 넓이하고 같으면

가희는 위에서 자는게 아니고, 적으면, 가희가 위에서 자는것이다.

import sys

input = sys.stdin.readline
N = int(input())
M = int(input())

graph = [[0 for _ in range(N+1)] for i in range(N+1)]
visited = [[True for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x][y] = 1



for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if start == end:
                continue
            if graph[start][mid] and graph[mid][end]:
                graph[start][end] = 1

result = []
for start in range(1,N+1):
    cnt = 0
    for end in range(1,N+1):
        if start == end:
            continue
        else:
            if not (graph[start][end] or graph[end][start]):
                cnt += 1
    result.append(cnt)
for row in result:
    sys.stdout.write(str(row)+'\n')

많이 해맸던 문제였다. 대소관계가 있는데 그걸 통해, 서로 비교가 불가능한 경우를 찾는 것을 어떻게 할지 고민을 많이했다.

플로이드 와샬을 통해 만들었다. 

대소 관계가 가능하다는 것은 

(1,2) (2,3) 이렇게 주어진다하면

그래프에서 graph[1][2],graph[2][3]에 1이 들어갈것이다.

그러면 플로이드 와샬을 통해, 두개의 그래프가 graph[start][mid], graph[mid][end] 가 전부 1이라고 했을때에만

start 가 end보다 크다는것을 알 수 있다.

이렇게 플로이드 와샬을 돌리고 난뒤에, 전체 N에 대해서 N번 돌려주면서, 서로 다른 두점의 그래프의 값이 전부 0이면, 

대소비교가 불가능한 경우이다. 이 경우를 전부 세어주면 문제를 풀 수 있다.

def get_prim_number(N):
    prime_check = [True]*(N+1)
    prime_check[0] = False
    prime_check[1] = True
    result = []

    for num in range(2,N+1):
        if prime_check[num]:
            result.append(num)
            for new_num in range(num*2,N+1,num):
                prime_check[new_num] = False
    
    return result


N = int(input())

prime_list = get_prim_number(N)
prefix_sum = prime_list[:]
for i in range(len(prime_list)-1):
    prefix_sum[i+1] += prefix_sum[i]

prefix_sum = [0] + prefix_sum


cnt = 0
left = 0
right = 0
while right <len(prefix_sum):
    temp = prefix_sum[right] - prefix_sum[left]

    if temp == N:
        cnt += 1
        right += 1
    elif temp < N:
        right += 1
    else:
        left += 1
        if temp == 0:
            left = right

print(cnt)

먼저 주어진 N까지의 소수들을 전부 구해준다.

그리고 구한 소수들을 prefix_sum으로 구간합을 구해준다.

두 포인터를 해주면 된다.

import math
import sys

input = sys.stdin.readline

def get_prim_number(N):
    prime_check = [True]*(N+1)
    prime_check[0] = False
    prime_check[1] = False
    result = []

    for num in range(2,int(math.sqrt(N))+1):
        if prime_check[num]:
            for new_num in range(num*2,N+1,num):
                prime_check[new_num] = False
    for num in range(2,N+1):
        if prime_check[num]:
            result.append(num)
    return result


N = int(input().strip())

prime_list = get_prim_number(N)
interval_sum = 0
left = 0
cnt = 0
for right in range(len(prime_list)):
    interval_sum += prime_list[right]

    while interval_sum > N:
        interval_sum -= prime_list[left]
        left += 1

    if interval_sum == N:
        cnt += 1

print(cnt)

위와 다른점은 소수를 구할때, 루트(N)까지만 반복을 해주는것과,

누적합을 미리 안 구하고, 앞에서부터 하나씩 더해가면서 right를 옮겨주고, N을 넘어가면 left를 늘려가면서 N인 경우를 찾아 주는 것이었다.

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
import heapq
input = sys.stdin.readline



N = int(input())
node_list = []
pay_list = []

for i in range(N):
    pay = int(input())
    heapq.heappush(node_list,(pay,i))
    pay_list.append(pay)


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

result = 0
visited = [False]*N
while node_list:
    pay,node = heapq.heappop(node_list)
    if visited[node]:
        continue
    visited[node] = True
    result += pay

    for next_node in range(N):
        if next_node != node:
            if pay_list[next_node] > connect_list[node][next_node]:
                pay_list[next_node] = connect_list[node][next_node]
                heapq.heappush(node_list,(pay_list[next_node],next_node))


print(result)

이 문제는 MST 문제로 기존의 MST와 다르게 여러개의 출발점을 동시에 가지는 MST라고 생각을 했다.

각 출발지점에 따라, 다른거이기 때문에 프림 알고리즘을 크루스칼 알고리즘보다 먼저 생각했다.

그래서 각 출발지점을 전부 입력으로 주어진 우물 개설비용으로 초기화 시켜준 점이 기존의 프림알고리즘하고

다른 방식이었다.

그리고 우물을 파는 비용,논의 위치를 heapq에 넣은듯 프림알고리즘을 해주었다.

그리고 방문 표시를 해서, 한번 들린곳은 다시 들리지 않도록 예외 처리를 해줬다.

기존의 MST에서 1곳의 출발지점을 정했던것과 달리, 모든 곳을 출발지점으로 생각하고, 비용을 갱신하면 되는 문제였다.

import sys

input = sys.stdin.readline

N = int(input())
edge = []
cost = []
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]


def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)

    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1

for i in range(N):
    pay = int(input())
    edge.append((pay,0,i+1))
    cost.append(pay)

arr = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    for j in range(i):
        edge.append((arr[i][j],i+1,j+1))



make_set = [i for i in range(N+1)]
rank = [0 for _ in range(N+1)]
edge.sort()
cnt = 0
result = 0
for pay,a,b in edge:
    if find_parent(a) != find_parent(b):
        cnt += 1
        result += pay
        union(a,b)
    if cnt == N:
        break
print(result)

크루스칼을 활용한 풀이이다.

여기서도 기존의 MST와 비슷하지만, 다른점은 물이 생성을 하는곳을 0이라는 인덱스를 부모로 가지도록

설정을 해주었다. 우물을 파서, 공급을 받는 곳은, 위치가 다를지라도, 물을 공급받고 있는 것이기 때문에

하나의 집합이라고 볼수 있기 때문이다. 이와 같은 작업을 N개가 이어질때까지 반복해주면 된다.

이 문제는 사실 https://boj.kr/10423 의 문제와 거의 동일하다고 볼 수 있다.