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

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

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

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

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

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

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

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

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

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

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

이와 같이

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

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

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

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

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

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만큼의 수를 이미 뺐다하면, 나머지 값들을 뒤에 붙여주면 된다.

# 11047 동전_0

N,K = map(int,input().split())
coins = []

for _ in range(N):
    coins.append(int(input()))
start = len(coins)-1
cnt = 0
while K > 0:
    if K - coins[start] >= 0:
        K -= coins[start]
        cnt += 1
    else:
        start -= 1


print(cnt)

이 문제는 목표하는 금액에서 내가 가지고 있는 큰 돈 부터 빼주면서 0보다 크거나 같으면 빼주면서 coin 번호를 하나씩 줄여주면서 풀었다.