Coding 공부

import sys
from collections import deque
 
def input():
    return sys.stdin.readline().rstrip()
A = list(input())
 
B = list(input())
N = len(A)
 
A.sort()
B.sort()
A = deque(A[:(N+1)//2])
B = deque(B[N-N//2:N])
answer = ['?']*N
left = 0
right = N-1
 
for idx in range(N):
    if idx%2:
        if A and A[0] >= B[-1]:
            answer[right] = B.popleft()
            right -= 1
        else:
            answer[left] = B.pop()
            left += 1
    else:
        if B and B[-1] <= A[0]:
            answer[right] = A.pop()
            right -= 1
        else:
            answer[left] = A.popleft()
            left += 1
 
 
print(''.join(answer))

문제를 보면, 구사과는 가장 사전순으로 빠르게,

큐브러버는 사전순으로 느리게이다.

이때 그냥 생각해보면 정렬하고, 

앞에서부터, 구사과는 작은걸

큐브러버는 큰걸 둔다고 생각을 하고 두면, 안된다.

이 문제는 최적의 방법이므로, 두사람의 패를 알고 있다고 가정을 하고 풀어야한다.

만약 구사과가 가진 문자열 중 가장 작은 것이, 큐브러버의 문자열중 가장 큰것보다, 작을때에는

작은걸 제일 앞에 두면 된다.

하지만 가장 작은것이 큐브러버 문자열 중 가장 큰것보다 크거나 같을때에는,

자신이 무조건 써야하는 패중에서 가장 큰걸 가장 뒤에 두는게 사전순으로 빠르게 하는방법이다.

이와 같이

큐브러버도 자신이 가진 문자열 중 가장 큰 것이, 구사과가 가진 가장 작은 문자열보다 클때에는 

앞에 자신의 가장 큰 문자열을 위치시키면 된다.

하지만 구사과가 가진 작은 문자열보다 자신이 가진 가장 큰 문자열이 작을때에는

자신이 가진 가장 작은 문자열을 뒤로 보내는것이, 사전순으로 늦게 하는방법일것이다.

이런식으로 해서 문제를 풀면된다.

M,N = map(int,input().split())
def string_fun(num):
    temp = []
    for st in num:
        temp.append(num_st[int(st)])
    return ''.join(temp)
arr = []
for num in range(M,N+1):
    arr.append(str(num))
 
num_st = ['zero','one','two','three','four','five','six','seven','eight','nine']
arr.sort(key=string_fun)
 
 
for i in range(len(arr)//10):
    print(*arr[i*10:(i+1)*10])
 
if len(arr)%10:
    for i in range(len(arr)-len(arr)%10,len(arr)):
        print(arr[i],end=' ')

sort에 key를 줘서 정렬을 했다.

N = int(input())
 
arr = list(map(int,input().split()))
 
arr.sort()
min_value = 0
if len(arr)%2:
    min_value = arr.pop()
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
else:
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
print(min_value)

정렬을 해주고, 가장 첫번째값과 가장끈값을 더한값의 최소값을 출력해주면 된다.

N = int(input())
 
arr = list(map(int,input().split()))
 
arr.sort()
min_value = 0
if len(arr)%2:
    min_value = arr.pop()
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
else:
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
print(min_value)

import heapq
def check(D):
    global result
    possible_set = []
 
    while rail_list:
        END,START = heapq.heappop(rail_list)
        if END-D <=START:
            heapq.heappush(possible_set,START)
        while possible_set and possible_set[0] < END-D:
            heapq.heappop(possible_set)
        
        result = max(result,len(possible_set))
 
 
 
 
N = int(input())
rail_list = []
for idx in range(N):
    A,B = map(int,input().split())
    if A > B:
        A,B = B,A
    heapq.heappush(rail_list,(B,A))
 
d = int(input())
result = 0
check(d)
print(result)

import heapq
 
N = int(input())
rail_list = []
for idx in range(N):
    A,B = map(int,input().split())
    if A > B:
        A,B = B,A
    rail_list.append((A,B))
rail_list.sort(key=lambda x : x[1])
 
in_rail = []
d = int(input())
result = 0
for start,end in rail_list:
    if end-d <= start:
        heapq.heappush(in_rail,start)
    while in_rail and end-d > in_rail[0]:
        heapq.heappop(in_rail)
    result = max(result,len(in_rail))
print(result)

N,K = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
diff = [0]*N
for i in range(N-1):
    diff[i] = arr[i+1] - arr[i]
 
diff.sort()
print(sum(diff[:len(diff)-(K-1)]))

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())
K = int(input())
arr = list(map(int,input().split()))
arr.sort()
diff = [0]*N
for i in range(N-1):
    diff[i] = arr[i+1] - arr[i]
 
diff.sort()
print(sum(diff[:len(diff)-(K-1)]))