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

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

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

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

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

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

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

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

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

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

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

이와 같이

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

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

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

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

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

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

def pop(queue,flag):
    if flag:
        return queue.pop()
    else:
        return queue.popleft()
T = int(input())

for _ in range(T):
    commands = list(input())
    N = int(input())
    if N:
        arr = deque(input().replace('[','').replace(']','').split(','))
    else:
        input()
        arr = deque()
    # 0 정방향 1 역방향
    flow = 0
    flag = True
    for command in commands:
        if command == 'R':
            flow = (flow+1)%2
        else:
            if arr:
                pop(arr,flow)
            else:
                flag = False
                break
    if flag:
        if flow:
            arr.reverse()
        print(f'[{",".join(arr)}]')
    else:
        print('error')

이 문제는 deque를 통해, 역방향인지 정방향인지에 따라 나눠서 결정을 지으면 되는 문제였다.

정방향인지 역방향인지에 따라 pop을 하는 위치를 바꿔주고, 최종 결과를 출력을 할때에도, 구분을 해줬다.

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를 줘서 정렬을 했다.

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

cnt = 0
total_dict = Counter()
while True:
    name = input()
    if not name:
        break
    total_dict[name] += 1
    cnt += 1

key_list = sorted(total_dict.keys())

for key in key_list:
    print(f'{key} {total_dict[key]*100/cnt:.4f}')

이 문제는 골드5라 되어있지만, 실버 수준인것 같다.

어려운 알고리즘도 없고, 단순히 formating을 이용한 반올림을 하면 된다.

전체 수를 딕셔너리에 저장을 하고, 정렬을 한뒤에 4자리까지만 출력되게 하면 된다.

from datetime import datetime
from collections import defaultdict
import sys
input = sys.stdin.readline

def convert_L(L):
    day,arg = L.split('/')
    day = int(day)
    hour,min = map(int,arg.split(':'))
    total_min = min + hour*60 + day*24*60
    return total_min

N,L,F = list(input().split())
N = int(N)
F = int(F)
L = convert_L(L)
part_manager_dict = defaultdict(dict)

tardy_dict = defaultdict(int)
for _ in range(N):
    total_string = input()
    time_string = total_string[:16]
    time_S = datetime.strptime(time_string,'%Y-%m-%d %H:%M')
    part_name,person = total_string[16:].split()
    if part_manager_dict[person].get(part_name):
        borrowed_time = time_S - part_manager_dict[person][part_name]
        day = borrowed_time.days
        min = borrowed_time.seconds//60
        to_time = day*60*24 + min
        if to_time > L:
            tardy_dict[person] += (to_time-L)*F
        del part_manager_dict[person][part_name]
    else:
        part_manager_dict[person][part_name] = time_S


if len(tardy_dict.keys()):
    key_list = sorted(tardy_dict.keys())

    for key in key_list:
        print(key,int(tardy_dict[key]))

else:
    print(-1)

문제에 주어진 조건대로 빌리시간을 저장해놓고, 반환한 시간에 그 차이를 통해 지각을 하면, 지각을 한 비용을 추가해주면 된다.

여기서 python 유저들이 주의해야할점은 datetime 모듈이나 time 모듈을 쓰면 시간초과가 날 수가 있으니 조심해야하는 것이다.

제일 좋은 방법은 이 문제는 2021년으로 한정짓고 있기 때문에 문자열을 파싱해서 직접계산하는것이 더 빠를 것이다.

근데 파싱하는게 귀찮으므로, 이 풀이는 넘어가겠다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def dfs(idx):
    if idx >= N:
        return 0

    if dp[idx] != -1:
        return dp[idx]
    max_value = 0
    for string_key in score_dict.keys():
        score,len_string = score_dict[string_key]
        if idx + len_string-1<N:
            for check_idx in range(len_string):
                if input_string[check_idx+idx] != string_key[check_idx]:
                    break
            else:
                max_value = max(max_value,score + dfs(idx+len_string))
    max_value = max(max_value,1+dfs(idx+1))
    dp[idx] = max_value
    return dp[idx]
                

input_string = input()
N = len(input_string)
M = int(input())
score_dict = {}
for _ in range(M):
    string,score = input().split()
    score_dict[string] = [int(score),len(string)]



dp = [-1]*(N+1)

print(dfs(0))

문제를 푼 방식은 다음과 같다.

문제에 주어진 문자열들을 문자열을 key로 하고, 점수와 길이를 value로 하는 dictionary에 넣어둔다.

그리고 0번인덱스부터 재귀를 돌면서

현재 위치에서부터 문자열이 일치하는 경우에 재귀를 하면서 최대값을 구한다.

그리고 일치하지 않을때를 위해, dfs(idx+1)+1 현재위치의 문자열만을 제거했을때도 구해주면된다.

그리고 dp값을 변환시켜주면 된다.

import sys
import bisect
def time_str_num(times):
    return times[:4]+times[5:7]+times[8:10]+times[11:13]+times[14:16]+times[17:19]

input = sys.stdin.readline

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

lev_list = [[] for _ in range(7)]
for _ in range(N):
    times,lev = input().split('#')
    times = time_str_num(times)
    lev_list[int(lev)].append(times)

result = []

for _ in range(Q):
    s_time,e_time,lev = input().split('#')

    s_time = time_str_num(s_time)
    e_time = time_str_num(e_time)
    lev = int(lev)
    cnt = 0
    for cu_lev in range(lev,7):
        s_ind = bisect.bisect_left(lev_list[cu_lev],s_time)
        e_ind = bisect.bisect_right(lev_list[cu_lev],e_time)
        cnt += (e_ind-s_ind)

    result.append(cnt)


for i in range(Q):
    sys.stdout.write(str(result[i])+'\n')

대회때 시간초과가 났던 문제다.

이 문제는 https://programmers.co.kr/learn/courses/30/lessons/17676 와 https://programmers.co.kr/learn/courses/30/lessons/72414 에서 비슷한 느낌을 받았던 문제이다.

이 2문제 전부 긴 시간대를 주고 문제에 주어진 것에서 최대값을 찾던가, 시간내에 있는 기록등을 찾는 방식이다.

이 문제 또한, 각종 로그들이 특정시간대에 나고, 시작시간과 종료시간 내에 발생한 로그의 개수를 세는 것이다.

푸는 방식은 다음과 같다. 레벨별로 시간을 나눠서 저장을 하는것이다.

어차피 들어오는 로그는 순서대로 들어오기 때문에, 작은순서대로 정렬되어서 들어가진다.

또한 년월일시분초를 다 합쳐서 14글자의 숫자로 저장해주면, 문자열로 저장해놔도, 대소구분이 되기 때문에 괜찮다.

그러면 문제에 주어진 로그들을 맞는 레벨에 하나씩 추가를 해준다.

그리고 로그가 들어오면 시작시간과 끝시간을 분리를 해놓는다.

그리고 이분탐색을 통해, 시작시간은 이 시간이 들어가야할 최소 위치,

끝시간은 이 시간이 들어갈수 있는 최대 위치를 구해준다.

위와 같은 리스트가 있다고 하고,

시작시간은 3이고, 끝시간은 4라 한다면,

시작시간은 2번인덱스을 가리켜야하고, 끝시간은 8번 인덱스를 가리켜야한다.

그러면, 8-2 = 6개가 나오는 걸 볼 수 있다.

이걸 나는 python에서 이분탐색을 위한 라이브러리인 bisect를 이용해서 bisect_left와 bisect_right를 통해 구현을 했다.

그리고 주어진 로그의 레벨이상을 전부 구하는 것이므로, 주어진 레벨에서부터 최대레벨인 6까지 전체 탐색을 해주었다.

import sys
import bisect
def time_str_num(times):
    return times[:4]+times[5:7]+times[8:10]+times[11:13]+times[14:16]+times[17:19]

input = sys.stdin.readline

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

lev_list = [[] for _ in range(7)]
for _ in range(N):
    times,lev = input().split('#')
    times = time_str_num(times)

    for i in range(1,int(lev)+1):
        lev_list[i].append(times)

for _ in range(Q):
    s_time,e_time,lev = input().split('#')

    s_time = time_str_num(s_time)
    e_time = time_str_num(e_time)
    lev = int(lev)
    cnt = 0
    s_ind = bisect.bisect_left(lev_list[lev],s_time)
    e_ind = bisect.bisect_right(lev_list[lev],e_time)
    cnt += (e_ind-s_ind)

    sys.stdout.write(str(cnt)+'\n')

   이 풀이는 위의 풀이와 똑같지만, 반복작업을 없애준 것이다.

 처음 로그가 들어올때부터, 1레벨부터 현재 레벨까지 전부 넣어주는것이다.

어차피 레벨 이상의 쿼리를 전부 조회하는 것이므로, 로그로 들어온 레벨 이하에 전부 저장을 해주고,

이분 탐색을 한번만 해서 출력할 수 있도록 해준 것이다.

대회시간에는 못 풀었지만 류호석님의 조언을 듣고 바로 풀 수 있었던 문제였다.

이전에 풀었던 문제들을 조금만 응용하면 풀수 있는 문제였지만, 제대로 응용하지 못한 패착인것 같다.

import sys

R,C = map(int,input().split())

GR,GC,PR,PC = map(int,input().split())


arr = []
P_total = PR*PC
for _ in range(R):
    temp = list(input())
    P_total-=temp.count('P')
    arr.append(temp)

if P_total:
    print(1)
else:
    print(0)

대회 때에는 너무 어렵게 생각해서 dfs,bfs를 이용해서 전체 베개의 개수를 구하는 방식으로 풀었는데,

대회 끝나고 간단한 풀이는 count로 P의 개수를 세주고, 그게 전체 배게의 넓이하고 같으면

가희는 위에서 자는게 아니고, 적으면, 가희가 위에서 자는것이다.