[BOJ] 21774 가희와 로그 파일

처음 문제를 읽고 든 생각은 탐색 문제라는 것이고 for문 2개로 하기에는 입력값이 너무 크므로 다른 방법을 사용해야 된다고 생각했습니다. 시간이 정렬되어 들어오고 중복된 값도 존재하는 것을 보고 이분 탐색을 써야겠다고 생각했습니다. 그리고 입력들어오는 형태 그대로 대소비교를 해도 괜찮은 형태로 들어오므로 그대로 사용하기로 결정했습니다.((2021-04-05 17:17:11<2021-04-05 17:18:11)==True) 그리고 파이썬 특유의 느린 입력? 을 해결하기 위해서 무조건 input을 readline으로 바꿔줬습니다.

그래도 혹시 모르니까 전부 돌아보는 방법을 할 수 있는 한 최적화해서 돌려보았습니다.

from sys import stdin

input=stdin.readline

n,q=map(int,input().split())

arr={i+1:[] for i in range(6)}

for i in range(n):
    date,lv=input().rstrip().split('#')
    arr[int(lv)].append(date)

for i in range(q):
    start,end,lv=input().rstrip().split('#')
    cnt=0
    for i in range(int(lv),7):
        if arr[i] and not(arr[i][0]>end or arr[i][-1]<start) :
            for j in range(len(arr[i])):
                if start<=arr[i][j]<=end:
                    cnt+=1
    print(cnt)

결과는 당연히 시간 초과였습니다..

저렇게 6개의 배열에 나누어서 담은 이유는 문제 입력에 시간순으로 입력된다고는 써 있으나 같은 시간에 여러 로그가 발생할수 있다고 하였습니다.  그런데 입력이 이 같은 시간에 레벨도 시간순으로,

# 레벨도 순서대로
2021-04-05 17:17:11#1
2021-04-05 17:17:11#2
2021-04-05 17:17:11#3
2021-04-05 17:17:11#4
# 시간만 순서대로
2021-04-05 17:17:11#3
2021-04-05 17:17:11#2
2021-04-05 17:17:11#1
2021-04-05 17:17:11#4

둘 중 어떤 식으로 작동할지에 대한 설명은 없는 것 같고, 탐색할 때 3레벨 이상을 찾아야 하는데 1,2레벨을 포함해서 전체 배열을 돌리는 것은 비효율적이라 생각해서 lv별로 분류해놓은 배열에 넣어주었습니다. 이렇게 함으로써 한 배열안에는 존재하는 시간은 더이상 중복도 안되므로 무지성 이분탐색을 통해 start와 end의 위치를 구할 수 있습니다

그러나 lower bound 라는 것을 배워볼겸 이것으로 풀어보기로 했습니다. lower bound는 들어갈수 있는 가장 작은 자리?를 알아내는 것이므로 end와 겹치는 시간대에 로그가 존재할 경우 문제가 발생하였습니다.

start=1 , end=3 , arr=[1,2,3,4]
lower bound를 통해 얻은 넣을 곳 arr=[start,1,2,end,3,4]
실제로 내가 필요한 것 arr=[start,1,2,3,end,4]

이것을 고치기 위해서 end를 구할때 upper bound라는 것을 사용해도 됐지만 함수를 두개까지 쓰고싶지 않아서 다른 방법을 생각해냈습니다.

start=1 , end=3 , arr=[1,2,3,4]
end+=0.5
lower bound를 통해 얻은 넣을 곳 arr=[start,1,2,3,end,4]
실제로 내가 필요한 것 arr=[start,1,2,3,end,4]

다른 값에 영향을 주지 않는 값을 뒤에 붙여주는 꼼수?를 써서 원하던 위치에 들어가도록 바꿔주었습니다.

최종 코드

from sys import stdin
input=stdin.readline

n,q=map(int,input().split())

arr={i+1:[] for i in range(6)}

def b(value,level,l):
    s=0
    e=l
    while s<e:
        mid=(s+e)//2
        if arr[level][mid]==value:
            e=mid
        elif value < arr[level][mid]:
            e=mid
        elif arr[level][mid]<value:
            s=mid+1
    return e

for i in range(n):
    date,lv=input().rstrip().split('#')
    arr[int(lv)].append(date)

for i in range(q):
    start,end,lv=input().rstrip().split('#')
    cnt=0
    for i in range(int(lv),7):
        cnt+=b(end+'',i,len(arr[i]))-b(start,i,len(arr[i]))
    print(cnt)

파이썬 맞은사람에서 다른 사람들의 코드를 보니 bisect라는 라이브러리를 사용하는 것을 보고 bisect 모듈을 사용해 한번 더 풀어보았습니다.

from sys import stdin
import bisect

input=stdin.readline

n,q=map(int,input().split())

arr={i+1:[] for i in range(6)}

for i in range(n):
    date,lv=input().rstrip().split('#')
    arr[int(lv)].append(date)

for i in range(q):
    start,end,lv=input().rstrip().split('#')
    cnt=0
    for i in range(int(lv),7):
        if arr[i]:
            s_idx=bisect.bisect_left(arr[i],start)
            e_idx=bisect.bisect_right(arr[i],end)
            cnt+=e_idx-s_idx
    print(cnt)

굉장히 코드가 깔끔해졌습니다.