이 문제는 접근은 바로 했는데 한 날짜를 계산하는 포인트에서 막혀서 상당히 버벅거리다 다른 풀이를 보고 빠르게 해소되었다. 그래서 다시는 잊지 않고자 이렇게 풀이를 쓴다.
문제를 요약하면 다음과 같다. 로그에 처리시간과 걸린시간이 주어진다. 그렇다면 1초간 얼마나 많은 트래픽을 처리할 수 있는지 확인하고자 한다. 로그는 날짜순으로 오름차순으로 제공된다.
위와 같은 그림을 보면 각 초마다 매번 확인을 하며 로그를 확인해야하는가 싶다. 그렇게 된다면 24시간을 초당 루프를 돌아야하고 더구나 각 로그가 속하는지도 확인을 해야한다. 다행인건 주어지는 로그가 오름차순으로 정렬되어 있다는 점이다. 이를 통해 문제 해결의 실마리를 찾을 수 있다. (각 구간에 속하기만 하면 된다. )
따라서 로그1이 존재할때 로그 1을 포함하는 1초의 최대 범위를 생각해보면 로그1의 종료시간을 포함하는 1초이면 된다. (위의 그림의 (2)번과 같다.)그러면 로그1~2000까지 한번의 루프와 이하의 n~2000까지의 루프만 돌면 되기 때문에 시간 복잡도가 줄어든다.
따라서 로그n을 기준으로 (로그n종료시간)~(로그n종료시간+1초)의 범위에 드는 n이하의 로그들의 개수의 최댓값을 구하면 된다.
그러면 순서는 다음과 같다. 우선 모든 로그의 값을 연산해야하기 때문에 연산하기 편한 정수형으로 만들어주고, 각 로그의 end값을 토대로 범위를 만들고, 이하의 로그들을 확인하며 구간에 들어가는 로그들의 개수를 찾는다.
1. 시간을 정수형으로 변환 후 배열에 저장
2. 로그별로 로그를 포함하는 end값부터 1초까지의 범위 구하기
3. 로그들을 확인하며 구간에 포함되는 경우 count 증가
4. count의 최대값을 저장
"""
각 end구간을 기준으로 범위를 비교하면
개수가 2000개 이므로 N*2*(시작이 포함되는 경우까지만)
"""
def get_time(time):
hour = int(time[:2]) * 3600
minute = int(time[3:5]) * 60
second = int(time[6:8])
millisecond = int(time[9:])
return (hour + minute + second) * 1000 + millisecond
def get_start_time(time, duration):
n_time = duration[:-1]
int_duration = int(float(n_time) * 1000) # 1000ms가 최대
return get_time(time) - int(int_duration) + 1
def solution(lines):
times = []
for t in range(len(lines)):
tline = lines[t]
date, time, sec = tline.split()
print(date, time, sec)
end = get_time(time)
start = get_start_time(time, sec)
times.append([start, end])
# 구간 비교 시작
big = 0
for t in range(len(lines)):
# 1분 구간 구하기
count = 0
start, end = times[t]
for n in range(t, len(lines)):
start = times[n][0]
if end > start - 1000:
count += 1
big = max(big, count)
print(big)
return big
* 코드 끝부분에 end > start -1000 로 구간을 확인할수 있는데, 처음에는 잘 이해가 안갔다.
만약 end, end+1000이라는 구간이 있을때 가능한 케이스는 아래와 같다.
그럼 차례대로 생각해보면 다음 로그의 start는 반드시 end+1000보다 작으면 원하는 구간에 속하게 된다.
즉, n_start < end+1000 이면 구간에 속한다고 볼 수 있고, 이게 end > start-1000이 된것이다.
결론 : 시간 연산은 정수형으로 바꾸어 풀면 좋다. 상황에 따라 sec단위나 ms단위로 바꾸면 연산이 편해진다.
'알고리즘' 카테고리의 다른 글
[python3] 백준 2470 풀이 ( 투포인터 ) (0) | 2022.02.25 |
---|---|
[python3] 프로그래머스 섬 연결하기 ( 그리디, MST, 크루스칼, 유니온 파인드) (0) | 2022.02.25 |
[python3] 백준 1194 풀이 ( "달이 차오른다, 가자." , BFS ) (0) | 2021.10.16 |
[python3] 백준 1005 풀이 ( ACM Craft, 위상정렬, 다이나믹 프로그래밍, DP ) (0) | 2021.08.28 |
[python3] 백준 1238 풀이 ( 파티, 다익스트라 ) (0) | 2021.08.28 |