Coding 공부

# 7576번 문제 
# 1은 익은 토마토 0은 익지않은 토마토

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

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

dx = [-1,1,0,0]
dy = [0,0,1,-1]
tomatocnt = 0
total = N*M
tomato = []
for x in range(M):
    for y in range(N):
        if tomatoarray[x][y] == 1:
            tomato.append((x,y))
            tomatocnt += 1
        elif tomatoarray[x][y] == -1:
            total -= 1
result = -1
day = 0
if total == tomatocnt:
    result = 0
else:
    while tomato:
        new_tomato = []
        for x,y in tomato:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<M and 0<=ny<N:
                    if not tomatoarray[nx][ny]:
                        tomatoarray[nx][ny] = 1
                        new_tomato.append((nx,ny))
                        tomatocnt += 1


        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomato = [row[:] for row in new_tomato]
        else:
            result = -1
            break



print(result)

BFS를 활용해 day별로 새로 토마토가 된 곳을 찾아서 해주었다. 

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

number =list(input())


result = [number[0]]
idx = 1
while K and idx <N:
    while result and K and number[idx] > result[-1]:
        result.pop()
        K -= 1
    result.append(number[idx])
    idx += 1
for _ in range(K):
    result.pop()
result = result + number[idx:]
print(''.join(result))

기본적인 원리는 다음과 같다.

반복문을 돌리면서 result에 마지막수보다 새로들어온 값이 클시에는 그 값들을 하나씩 빼준다. 그리고 난뒤 append를 해준다.

이렇게 끝까지 갔는데도, K가 남아있을시에는 남은 K만큼 pop을 해준다.

그리고, 만약 끝까지 가지 않았는데도, K만큼의 수를 이미 뺐다하면, 나머지 값들을 뒤에 붙여주면 된다.

N = int(input())
arr = list(map(int,input().split()))
LIS = [arr[0]]
parents = [-1]*N
parents[0] = 0
temp = 0
for i in range(1,len(arr)):
    if arr[i] > LIS[-1]:
        parents[i] = len(LIS)
        LIS.append(arr[i])
    else:
        start = 0
        end = len(LIS)
        idx = len(LIS)-1
        while start < end:
            mid = (start+end)//2
            if LIS[mid] >= arr[i]:
                idx = min(idx,mid)
                end = mid
            else:
                start = mid + 1
        LIS[idx] = arr[i]
        parents[i] = idx

LIS_CNT = len(LIS)
result = [-1]*LIS_CNT

for i in range(N-1,-1,-1):
    if parents[i] == LIS_CNT-1:
        result[LIS_CNT-1] = arr[i]
        LIS_CNT -= 1
print(len(result))
print(*result)
    
# https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

위의 블로그를 참조해서 코드를 풀었다.

기본적인 원리는 다음과 같다. LIS를 구하면서 parents라는 배열에 해당 LIS에 들어갔던 idx를 저장해준다.

그리고 난뒤 마지막에 LIS의 크기에서부터 하나씩 내려가면서 그에 맞는 배열 값들을 찾아주면 된다.

from collections import deque
import sys
input = sys.stdin.readline

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


AppendList = [list(map(int,input().split())) for _ in range(N)]
tree_info = [[[] for _ in range(N)] for _ in range(N)]
result = 0
forest = [[5]*N for _ in range(N)]

for _ in range(M):
    X,Y,age = map(int,input().split())
    tree_info[X-1][Y-1].append(age)
    result += 1

dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]
for year in range(K):

    for x in range(N):
        for y in range(N):
            if len(tree_info[x][y])>0:
                temp = []
                summer_forest = 0
                cnt = 0
                limited = len(tree_info[x][y])
                while cnt < limited:
                    age = tree_info[x][y].pop()

                    if forest[x][y] >= age:
                        forest[x][y] -= age
                        temp.append(age+1)
                    else:
                        summer_forest += (age//2)
                        result -= 1
                    cnt += 1
                temp.sort(reverse=True)
                tree_info[x][y].extend(temp)
                forest[x][y] += summer_forest
            forest[x][y] += AppendList[x][y]
    for x in range(N):
        for y in range(N):
            spread_cnt = 0
            if tree_info[x][y]:
                for val in tree_info[x][y]:
                    if val%5 == 0:
                        spread_cnt += 1

            if spread_cnt:
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<N and 0<=ny<N:
                        result += spread_cnt
                        tree_info[nx][ny].extend([1]*spread_cnt)
print(result)

 구현을 하는 문제인데, 문제에 주어진 조건대로 면 된다. 문제는 시간초과의 벽이 너무 컸다. 시간초과가 나지 않도록 최대한 문제에 주어진 조건을 한번에 구현할수 있도록 하는게 중요했다.

import sys
input = sys.stdin.readline
N,M,K  = map(int,input().split())
store = [list(map(int,input().split())) for _ in range(N)]
tree_info = [[{} for _ in range(N)] for _ in range(N)]
forest = [[5]*N for _ in range(N)]

tree_cnt = 0
for _ in range(M):
    x,y,age = map(int,input().split())
    tree_info[x-1][y-1][age] = 1
    tree_cnt += 1

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

for _ in range(K):
    for x in range(N):
        for y in range(N):
            if tree_info[x][y]:
                summer_forest = 0
                new_dict = {}

                for age in sorted(tree_info[x][y].keys()):
                    if forest[x][y] >= age * tree_info[x][y][age]:
                        forest[x][y] -= age * tree_info[x][y][age]
                        new_dict[age+1] = tree_info[x][y][age]
                    else:
                        if forest[x][y] // age:
                            new_dict[age+1] = forest[x][y]//age
                            forest[x][y] -=  age*new_dict[age+1]
                            if tree_info[x][y][age] - new_dict[age+1]:
                                summer_forest += (age//2) * (tree_info[x][y][age] - new_dict[age+1])
                                tree_cnt -= (tree_info[x][y][age] - new_dict[age+1])
                        else:
                            summer_forest += (age//2)*tree_info[x][y][age]
                            tree_cnt -= tree_info[x][y][age]
                tree_info[x][y] = new_dict
                forest[x][y] += summer_forest
            forest[x][y] += store[x][y]
    for x in range(N):
        for y in range(N):
            spread_cnt = 0
            for age in tree_info[x][y]:
                if not age%5:
                    spread_cnt += tree_info[x][y][age]
            if spread_cnt:
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx <N and 0<=ny<N:
                        if tree_info[nx][ny].get(1):
                            tree_info[nx][ny][1] += spread_cnt
                        else:
                            tree_info[nx][ny][1] = spread_cnt
                        tree_cnt += spread_cnt
print(tree_cnt)

import heapq
import sys

input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    temp = list(map(int,input().split()))
    for number in temp:
        heapq.heappush(arr,number)
    while len(arr) > N:
        heapq.heappop(arr)



result = heapq.heappop(arr)
print(result)

문제의 조건 중 N이 1500이라서 전부 arr에 저장을 하면 메모리가 부족할 가능성이 있다.

그래서 arr의 크기를 N으로 고정시켜놓고 그보다 클시에는 pop을 해주는 방식으로 했다.

import heapq
import sys

input = sys.stdin.readline

N = int(input())
arr = []

for i in range(N):
    input_list = map(int,input().split())
    if i == 0 :
        for number in input_list:
            heapq.heappush(arr,number)
    else:
        for number in input_list:
            if number > arr[0]:
                heapq.heappushpop(arr,number)
big_list = heapq.nlargest(N,arr)
print(big_list[N-1])

 두번째 방식은 heapq의 기능을 좀 더 잘 쓰는것이다.

heappushpop을 하면 heapop을 하고 heappush를 하는 것보다 더 빠르다.

이걸 이용해서 위와 같이 똑같이 해주고,

마지막에는 전체 arr 중에서 N개의 큰 수 만을 뽑아내는 methods를 활용해준다.

# stkang9409 풀이 해석

def find_max_value(x):
    return arr[max_row_list[x]][x]

import sys

input = sys.stdin.readline


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

max_row_list = [N-1]*N
# 각 열마다 가장 큰 값은 N-1번 행에 있는 값이다.
# 매번 돌면서 각 열마다 가장 큰값들을 비교해, 가장 큰 값이 있는 열의 index 값을 하나씩 줄여나간다.
# 그렇게 하면 마지막 N번째에 가장 큰 값을 가지는 열의 값이 N번째로 큰 수의 열값이 되고
# 그 때 저장된 위치의 값이 행이된다.
for cnt in range(N):
    max_col_index = 0
    for col in range(N):
        max_col_index = max(col,max_col_index,key= find_max_value)
    if cnt == N-1:
        print(arr[max_row_list[max_col_index]][max_col_index])
    max_row_list[max_col_index] -= 1

다른 분의 풀이를 해석한 것으로, 문제의 조건을 활용해서 하는 방식이다.

각 열의 값은 다음 행의 값보다는 작다는 점을 이용해,

N번을 반복하면서 가장 큰 값들이 위치한 col의 row값을 하나씩 줄여주는 방식이다.

N = int(input())
K = int(input())
ST,EN = 1,K
while ST<=EN:
    mid = (ST+EN)//2
    cnt = 0
    for i in range(1,N+1):
        cnt += min(mid//i,N)

    if cnt < K:
        ST = mid + 1
    else:
        EN = mid -1

print(ST)

코드는 간단하지만 어려운 문제였다.

기본적인 원리는 이러하다. 

N*N 행렬이 있고, 그 안의 값은 해당 row index와 col index의 곱이 된다.

그렇다면 해당 줄에서 주어진 값 X보다 작은 값은 row_index로 나눈 몫일것이다.

만약 N = 5 이고 주어진 X가 12라면,

1행 : 1,2,3,4,5

2행 : 2,4,6,8,10

3행 : 3,6,9,12,15

4행 : 4,8,12,16,20

5행 : 5,10,15,20,25

이다. 이럴때 12보다 작은 값들은 1행에 5개, 2행에 5개 3행에 4개 4행에 3개 5행에 2개이다.

즉 12를 row의 index로 나눈 몫과 동일하다.

이를 통해, cnt가 K개가 될수 있는 X를 찾아주면 된다.

그리고 초기 값의 END가 K인 이유는 K번째 수는 K보다 작거나 같기 때문이다.

import sys
sys.setrecursionlimit(10000)
def dfs(node):
    if not graph[node]:
        return 0
    ind = 0
    for next_node in graph[node]:
        distance_nodes[node][ind] += dfs(next_node) + graph[node][next_node]
        ind += 1
    return max(distance_nodes[node])
N = int(input())
graph = [{} for _ in range(N+1)]
parents = [0]*(N+1)
for _ in range(N-1):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    parents[A] += 1

distance_nodes = [[0]*(parents[ind]+2) for ind in range(N+1)]

dfs(1)
result = 0
for ind in range(1,N+1):
    distance_nodes[ind].sort(reverse=True)
    result = max(result,distance_nodes[ind][0]+distance_nodes[ind][1])
print(result)

첫 풀이방식은 다음과 같았다. 각 노드에서 가장 긴 노드들을 더해주는 방식이었다. 리프노드에 도착하면 0을 반환해주고 

재귀를 활용해서, 현재의 노드에서 자식노드까지의 거리 + 그 자식노드의 재귀함수를 통해 최대값을 더해주는 방식으로 했다.

이렇게 모든 노드들에 대해서 거리들을 전부 구한뒤, 모든 노드들의 거리의 합이 최대가 되는것을 구해주었다.

import sys
input = sys.stdin.readline
def dfs(ind):
    global N,result,max_Node
    visited = [True]*(N+1)
    stack = []
    stack.append((ind,0))
    visited[ind] = False
    while stack:
        node, distance = stack.pop()
        if distance > result:
            result = distance
            max_Node = node
        if graph[node]:
            for next_node in graph[node]:
                if visited[next_node]:
                    visited[node] = False
                    stack.append((next_node,distance+graph[node][next_node]))


N = int(input())
graph = [{} for _ in range(N+1)]
for _ in range(N-1):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C

result = 0
max_Node = 0

dfs(1)
dfs(max_Node)
print(result)

두번째 방식은 훨씬 간단하다. 두번의 dfs로 풀리는데 다음과 같다.

어느 한 지점에서 제일 거리가 멀리 떨어진 곳에 위치 한 곳을 구하면, 그 지점이 트리의 지점을 구할 수 있는 한 점인 것을 알 수 있다.

왜냐하면, 지름은 해당 트리에서 제일 긴 곳은 지름일테고, 그렇기 때문에 그 안에 있는 점의 가장 먼거리를 가지는 점은 지름의 두 점 중 하나가 될것이다.

이걸 이용해서 첫번째 dfs에서 트리의 지름에 해당하는 한 점을 구하고,

그 점에서 dfs를 통해 최대거리를 구하면 답이 된다.

N,S = map(int,input().split())
arr = list(map(int,input().split()))
start,end = 0,0
temp = 0
result = float('inf')

while start <= end:
    if temp >= S:
        temp = temp - arr[start]
        result = min(result,end - start)
        start += 1
    elif end == N:
        start += 1
    else:
        temp = temp + arr[end]
        end += 1
if result == float('inf'):
    print(0)
else:
    print(result)

투 포인터를 활용한 문제이고, 투포인터를 이용해서, 주어진 S 값이 넘어갔을때 최소 길이를 비교해주는 방식으로 했다.