Coding 공부

from collections import defaultdict
 
N = int(input())
 
arr = list(input())
 
cnt_dict = defaultdict(int)
result = 0
prev_idx = -1
for idx in range(N):
    alpha = arr[idx]
    cnt_dict[alpha] = idx
    if len(cnt_dict) > N:
        min_idx = 100001
        min_key = -1
        for key in cnt_dict:
            if min_idx > cnt_dict[key]:
                min_idx = cnt_dict[key]
                min_key = key
        prev_idx = min_idx
        del cnt_dict[min_key]
    
    result = max(result,idx-prev_idx)
print(result)

전형적인 두 포인터 문제이고, 그걸 다른 방식으로 푼 것이다. 

defalutdict를 통해, 각 알파벳의 마지막 위치를 저장시켜주고,

그 길이가 N을 넘어서게 되면, 마지막 위치가 가장 작은 알파벳을 삭제해주는 방식으로 해주고

prev_idx를 갱신해준다

위와 같은 방식을 통해 문제를 풀어주면 된다.

   . 

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인 경우를 찾아 주는 것이었다.

N = int(input())
 
arr = list(map(int,input().split()))
 
arr.sort()
 
 
elsa_start = 0
elsa_end = N -1
result = float('inf')
 
for elsa_start in range(N-3):
    for elsa_end in range(elsa_start+3,N):
        anna_start = elsa_start + 1
        anna_end = elsa_end - 1
        elsa = arr[elsa_start] + arr[elsa_end]
        while anna_start < anna_end:
            anna = arr[anna_start] + arr[anna_end]
            temp = elsa-anna
            if result > abs(temp):
                result = abs(temp)
            
            if temp > 0:
                anna_start += 1
            else:
                anna_end -= 1
 
 
 
print(result)

첫 풀이는 ELSA와 ANNA로 나누는데, ELSA를 작은것을 1~N-3까지 그리고 큰 눈사람을 3~N 사이의 것을 고르고, 그 사이의 값에서 elsa anna의 격차가 작은걸 구했다.

def diffcheck(A,B):
    ss = set()
    ss.update(A)
    ss.update(B)
    if len(ss) == 4:
        return True
    return False
def getDiffHeight(A,B):
    elsa = arr[A[0]] + arr[A[1]]
    anna = arr[B[0]] + arr[B[1]]
    return abs(elsa-anna)
N = int(input())
 
arr = list(map(int,input().split()))
 
arr.sort()
 
stack = []
 
for i in range(N-1):
    for j in range(i+1,N):
        stack.append((i,j))
 
stack.sort(key=lambda x : arr[x[0]]+arr[x[1]])
result = float('inf')
for i in range(len(stack)-1):
    if diffcheck(stack[i],stack[i+1]):
        result = min(result,getDiffHeight(stack[i],stack[i+1]))
 
 
print(result)

두번째 풀이는 다음과 같다. 가능한 좌표의 조합을 다 구하고,

그 좌표의 조합에서 나오는 눈사람의 크기를 기준으로 정렬을 해준다.

그리고 그 4개의 고른 눈사람 좌표가 다르고, 그 격차가 작으면, 최저값으로 갱신해주는 것이다.

N,K = map(int,input().split())
 
arr = list(map(int,input().split()))
dp = [0]*(N+1)
result = 0
 
 
left = 0
right = 0
sum_temp = 0
while right <=N:
    if sum_temp >=K:
        while sum_temp >= K:
            dp[right] = max(dp[right],dp[left]+sum_temp-K)
            sum_temp -= arr[left]
            left += 1
    else:
        dp[right] = max(dp[right],dp[right-1])
        if right == N:
            break
        sum_temp += arr[right]
        right += 1
print(dp[N])
 

import sys
 
sys.setrecursionlimit(100001)
def find_min_right_over_k(left):
    global K
    low = left -1
    high = N
    while low + 1 < high:
        mid = (low+high)//2
        if prefix_sum[mid] - prefix_sum[left-1] >=K:
            high = mid
        else:
            low = mid
    return high
 
 
 
 
def solution(left):
    if left > N:
        return 0
    if dp[left] != -1:
        return dp[left]
    pass_hear_value = solution(left+1)
    right = find_min_right_over_k(left)
    eat_left_right = prefix_sum[right]-prefix_sum[left-1]-K+solution(right+1)
    max_value = max(pass_hear_value,eat_left_right)
    dp[left] = max_value
    return dp[left]
 
N,K = map(int,input().split())
 
arr = list(map(int,input().split()))
 
dp = [-1]*(N+1)
 
prefix_sum = [0]+arr[:]
for k in range(1,N+1):
    prefix_sum[k] += prefix_sum[k-1]
 
 
print(solution(1))

from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline
N, D,K,C = map(int,input().split())
a = defaultdict(int)
 
sushi = deque()
max_value = 0
# D 초밥의 가짓수
# K 는 연속해서 먹은 초밥의 수
# C 쿠폰번호
sushi_dict = defaultdict(int)
cnt = 0
sushi_list = [int(input()) for _ in range(N)]
for left in range(N+K+1):
    sushi_input = sushi_list[left%N]
    if len(sushi)<K:
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if len(sushi) == K:
            if sushi_dict[C]>0:
                max_value = max(max_value,cnt)
            else:
                max_value = max(max_value,cnt+1)
    else:
        remove_sushi = sushi.popleft()
        sushi_dict[remove_sushi] -= 1
        if sushi_dict[remove_sushi] == 0:
            cnt -= 1
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if sushi_dict[C]>0:
            max_value = max(max_value,cnt)
        else:
            max_value = max(max_value,cnt+1)
 
print(max_value)

import sys
 
input = sys.stdin.readline
 
N = int(input())
A= []
B = []
C = []
D = []
for _ in range(N):
    a,b,c,d = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
part_one = {}
for a in A:
    for b in B:
        if part_one.get(a+b):
            part_one[a+b] += 1
        else:
            part_one[a+b] = 1
answer = 0
for c in C:
    for d in D:
        temp_sum = -(c+d)
        if part_one.get(temp_sum):
            answer += part_one[temp_sum]
 
 
 
print(answer)

# skrud3021 님 코드 공부한거
N = int(input())
 
A,B,C,D = [],[],[],[]
 
 
for _ in range(N):
    a,b,c,d = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
 
 
ab_sum = [i+j for i in A for j in B]
ab_sum.sort()
ab_sum.append(2<<29+1)
cd_sum = [i+j for i in C for j in D]
cd_sum.sort(reverse=True)
cd_sum.append(2<<29+1)
ab_ind = 0
cd_ind = 0
result = 0
while ab_ind <N**2 and cd_ind<N**2:
    sum_mid = ab_sum[ab_ind] + cd_sum[cd_ind]
    if sum_mid > 0:
        cd_ind += 1
    elif sum_mid < 0:
        ab_ind += 1
    else:
        ab_start_ind = ab_ind
        cd_start_ind = cd_ind
        ab_value = ab_sum[ab_ind]
        cd_value = cd_sum[cd_ind]
        while ab_value == ab_sum[ab_ind]:
            ab_ind += 1
        while cd_value == cd_sum[cd_ind]:
            cd_ind += 1
        
        result = result + (ab_ind-ab_start_ind)*(cd_ind-cd_start_ind)
 
print(result)

N = int(input())
arr = [input() for _ in range(N)]
 
start = 0
end = N-1
 
result = []
 
while start <= end:
    if arr[start] < arr[end]:
        result.append(arr[start])
        start += 1
    elif arr[start] > arr[end]:
        result.append(arr[end])
        end -= 1
    else:
        next_start = start
        next_end = end
        flag = True
        while arr[next_end] == arr[next_start]:
            if next_end >0:
                next_end -= 1
            if next_start < N:
                next_start += 1
            if arr[next_start] < arr[next_end]:
                flag = True
            elif arr[next_start] > arr[next_end]:
                flag = False
 
        if flag:
            result.append(arr[start])
            start += 1
        else:
            result.append(arr[end])
            end -= 1
 
 
 
 
lens = len(result)
 
if lens <= 80:
    print(''.join(result))
else:
    for ind in range(lens//80+1):
        if ind == lens//80:
            print(''.join(result[ind*80:]))
        else:
            print(''.join(result[ind*80:(ind+1)*80]))