Coding 공부

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을 하는 위치를 바꿔주고, 최종 결과를 출력을 할때에도, 구분을 해줬다.

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
input = sys.stdin.readline
def permutation(ind,C,string_list,particle_order):
    global result
    if ind == C:
        if len(string_list)>0:
            result.add(''.join(string_list))
        else:
            result.add('EMPTY')
        return
    else:
        for i in range(1,N+1):
            command_order = particle_order[i]
            if command_order >= len(order_list[i]):
                continue
            else: 
                if not visited[i][command_order]:
                    order_num = order_list[i][command_order]
                    new_stringlist = string_list[:]
                    check_error = False
                    for order in card_command[order_num]:
                        if order[0] == 'ADD':
                            new_stringlist.append(order[1])
                        else:
                            remove_index = int(order[1])
                            if len(new_stringlist) > remove_index:
                                new_stringlist.pop(remove_index)
                            else:
                                check_error = True
                                break
                    if check_error:
                        result.add('ERROR')
                        continue
                    else:
                        visited[i][command_order] = True
                        particle_order[i] += 1
                        permutation(ind+1,C,new_stringlist,particle_order)
                        visited[i][command_order] = False
                        particle_order[i] -= 1


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

order_list = [[] for _ in range(N+1)]

for ind in range(1,N+1):
    input_list = list(map(int,input().split()))
    order_list[ind] = input_list[1:]



card_command = [[] for _ in range(C+1)]


for ind in range(1,C+1):
    commands = list(input().rstrip().split(','))
    temp = []
    for command in commands:
        new_command = list(command.split(' '))
        temp.append(new_command)
    card_command[ind] = temp

result = set()
visited = [[False for _ in range(len(order_list[ind]))] for ind in range(N+1)]
particle_order = [0 for _ in range(N+1)]
permutation(0,C,[],particle_order)
result = list(result)
result.sort()
for i in range(len(result)):
    sys.stdout.write(result[i]+'\n')

이 문제는 구현을 하면 되는 문제였다. 여기서 주의해야할 점은, 사람1이 소지한 순서대로 카드를 낸다는것이다.

그러므로 먼저 사람1~ 사람N 까지의 순열을 구하는데 느낌은 

사람이 가지고 있는 카드의 수만큼 중복되게 수를 구해주고 순열을 구해주는 느낌으로 풀면된다.

만약 사람1이 카드를 4장 사람2가 카드를 2장 사람3가 카드를 3장 가지고 있다고 하면

[1,1,1,1,2,2,3,3,3] 이런식으로 리스트를 만들어놓고 순열을 구해도 된다.

나 같은 경우엔 각 사용자별로 card_command에 각 명령어를 파싱해서 저장을 시켜주었다.

그리고 particle_order를 이용해서, 각 사용자가 몇번재 카드를 썼는지 확인을했다.

그 뒤에는 재귀를 이용해서 백트래킹을 해주었다.

particle_order의 숫자가 사람1의 전체 명령어 수와 같게 되면, 선택을 못하게 if문으로 판별을 해주었다.

prarticle_order가 각 사람의 명령어 수보다 적다면, 인제 이 명령어가 가능한지 판단을 한다.

명령을 수행하다가 error가 발생시, result에 add를 추가해주고, 다음번으로 넘어가준다.

그리고 명령을 정확하게 수행하면, visited[사람의 인덱스][그 사람의 몇번째 카드]에 방문을 표시를 해준다.

그리고 particle_order의 값을 1 늘려주고, 재귀를 해준다.

이렇게 재귀를 하면서 전체 카드수를 다 쓰면, 모든 명령을 잘 수행한것이 된다. 그러면 그때의 결과를 result에 추가하는데,

아무것도 안남아있으면 EMPTY를 추가해주면 된다.

그리고 재귀를 하다가 복귀하게 되었을때에는 visited를 초기화해주고, particle_order도 1을 빼주면 된다.

이 문제는 백트래킹을 어떻게, 그리고 순열을 어떻게 응용해서 하는지에 대한 문제였다.

그래서 긴 문제 지문에 비해 많이 어려운 편은 아니였다.

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레벨부터 현재 레벨까지 전부 넣어주는것이다.

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

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

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

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