Coding 공부

def solution(board, skill):
    answer = 0
    N = len(board)
    M = len(board[0])
    skill_board = [[0 for i in range(M+2)] for _ in range(N+2)]
    cnt = 0
    for sk in skill:
        sk_type, r1,c1,r2,c2 ,degree = sk
        if sk_type == 1:
            degree = -degree
        r1 +=1; r2+=1; c1+=1; c2+=1
        skill_board[r1][c1] += degree
        skill_board[r1][c2+1] -= degree
        skill_board[r2+1][c1] -= degree
        skill_board[r2+1][c2+1] += degree
    for x in range(1,N+1):
        for y in range(1,M+1):
            skill_board[x][y] = skill_board[x][y] + skill_board[x-1][y] + skill_board[x][y-1] - skill_board[x-1][y-1]
    for x in range(N):
        for y in range(M):
            if board[x][y] +skill_board[x+1][y+1] >0:
                answer += 1
    return answer

이 문제도 실전에서 풀지 못했던 문제였다.

7번 문제에 너무 힘을 쏟은 나머지, 마지막 20분동안 풀다가 범위 측정을 제대로 못해서, 풀지 못한 문제였다.

평소 2차원 누적합을 잘 다루지 않다보니, 범위를 구하는데 실수를 했고, 그 범위의 누적합을 구하는데 연산을 실후 했다.

이 문제에서 중요한 것은 폭발 범위에 맞춰서 누적합을 할 수 있게, 숫자들을 정리해 놓고, 누적합을 구하면 되는 문제이다.

폭발이 시작하는 r1,c1에는 +degree을 해주고,

폭발이 끝나는 위치인 r2+1,c1 , r1,c2+1에는 -degree을 해준다.

그리고 중요한 것은 r2+1, c2+1 에서는 +degree를 해주는 것이다.

이 누적합을 마킹해놓은 상태에서 가로로 1번 누적합 세로로 1번 누적합을 진행을 한다고 생각을 해보면, 왜 그 위치에서 마킹을 해줘야하는지 이해할 수 있다.

이 문제는 누적합이라는 접근까지 했지만, 디버깅 할 시간이 부족해 풀지 못했던 아쉬웠던 문제였다..

2차원 누적합은 매번 풀때마다, 햇갈려하는 유형이기 때문에 좀 더 연습해야겠다.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()

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

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


prefix_sum = [0] + arr[:]
result = 0
num_dict = defaultdict(int)
for i in range(1,N+1):
    prefix_sum[i] += prefix_sum[i-1]
    calc = prefix_sum[i] - M*i

    result += num_dict[calc]
    num_dict[calc] += 1


print(result+num_dict[0])

몇달 전에 푼 문제라 정확히 복기는 못하지만, 현재 생각 나는대로 복기를 할려고 한다.

 이 문제는 누적합을 이용해 구간의 평균합의 개수를 구하는 것이다.

현재까지의 누적합에서 지금까지의 평균의 총합을 빼주게 된다면, 

현재 위치에서 평균이 되기 위해 사라져야할 값이 보인다.

이 점을 이용해 푸는 문제이다.

구해야하는 평균이 K일때

즉 현재의 누적합 - 구간*K 을 했을때 나오는 값을 calc이라 했을 때,

이 calc 만큼만 사라지면 현재 구간 앞에서 얻을 수 있는 평균이 K인 구간의 개수가 되는 것이다.

이 문제는 누적합에서 구간의 평균합을 뺀 숫자와 일치하는 개수를 계속 누적해서 더해주면 풀 수 있는 문제이다.

그리고 마지막에 0을 더해준 이유는 현재 구간의 앞에서 나올 수 있는것을 더해준 것이니,

전체 구간에서 더해줄 필요가 있어서, 마지막에 더해주는 것이다.

6달전에 풀었던 것을 다시 복기할려니 정확하게 설명은 못했지만, 위와 같은 방법을 활용하면 된다.

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 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)