def make_pretty_time(time):
"""
time string을 밀리초 기준의 정수로 변환하여 반환
"""
hour, minute, second = time.split(":")
s, ms = map(int, second.split("."))
return int(hour) * 3600000 + int(minute) * 60000 + s * 1000 + ms
def solution(lines):
answer = 0
times = [] # 모든 처리시간의 시작 시간과 끝 시간을 저장할 리스트
for num, line in enumerate(lines):
date, end, period = line.split() # 날짜, 처리시간의 종료 시간, 처리시간
# 처리시간의 형태에 따라 정수로 변환하여 초와 밀리초를 기록
period = period[:-1].split(".")
if 1 < len(period):
s, ms = int(period[0]), int(period[1] + "0" * (3 - len(period[1])))
else:
s, ms = int(period[0]), 0
# (시작 시각 또는 끝 시각, 처리 인덱스, 처리 상태)를 튜플로 기록
times.append((make_pretty_time(end) - s * 1000 - ms + 1, num, "start"))
times.append((make_pretty_time(end), num, "end"))
times.sort()
num_set = set() # 현재 포함되어있는 처리 번호를 저장할 세트
for index, (time, num, status) in enumerate(times):
# 현재 구간 = time ~ time + 1000 밀리초
# 현재 구간에서 시작되거나 끝나는 처리 번호를 세트에 기록
while index < len(times) and times[index][0] < time + 1000:
next_time, next_num, next_status = times[index]
if next_num not in num_set:
num_set.add(next_num)
index += 1
answer = max(answer, len(num_set)) # 최댓값 갱신
# 만약 처리시간이 끝났다면 다음 시간 구간에서 현재 처리 번호는 포함되지 않아야 하므로
# 다음 for loop가 돌기 전 세트에서 현재 처리 번호를 제거
if status == "end":
num_set.remove(num)
return answer
times
리스트에 변환하여 처리의 인덱스 번호, 처리의 시작 또는 끝 상태를 튜플로 함께 저장한다.times
리스트에 기록된 시각에 대하여 특정 시각(time
)부터 1초 이내의 구간을 탐색한다. 탐색 중인 구간을 현재 구간
이라 한다.현재 구간
에 포함된 처리는 그 인덱스 번호를 기준 삼아 세트에 저장한다.현재 구간
에 포함된 처리는 시간 내에 시작되거나 끝이 난 처리(times[index][0] < time + 1000
)이다.num_set
에 저장한다.time
에 이루어진 처리가 해당 처리의 종료를 의미한다면(status == "end"
) 다음 time
에서는 이를 포함하지 않도록 num_set
에서 제거한다.7, 8, 9번 테스트 케이스를 통과하지 못하였다.
def make_pretty_time(time):
"""
time string을 밀리초 기준의 정수로 변환하여 반환
"""
hour, minute, second = time.split(":")
s, ms = map(int, second.split("."))
return int(hour) * 3600000 + int(minute) * 60000 + s * 1000 + ms
def solution(lines):
answer = 0
times = [] # 모든 처리시간의 시작 시간과 끝 시간을 저장할 리스트
for num, line in enumerate(lines):
date, end, period = line.split() # 날짜, 처리시간의 종료 시간, 처리시간
# 처리시간의 형태에 따라 정수로 변환하여 초와 밀리초를 기록
period = period[:-1].split(".")
if 1 < len(period):
s, ms = int(period[0]), int(period[1] + "0" * (3 - len(period[1])))
else:
s, ms = int(period[0]), 0
# (시작 시각 또는 끝 시각, 처리 인덱스, 처리 상태)를 튜플로 기록
times.append((make_pretty_time(end) - s * 1000 - ms + 1, num, "astart"))
times.append((make_pretty_time(end), num, "end"))
times.sort()
num_set = set() # 현재 포함되어있는 처리 번호를 저장할 세트
for index, (time, num, status) in enumerate(times):
# 현재 구간 = time ~ time + 1000 밀리초
# 현재 구간에서 시작되거나 끝나는 처리 번호를 세트에 기록
while index < len(times) and times[index][0] < time + 1000:
next_time, next_num, next_status = times[index]
if next_num not in num_set:
num_set.add(next_num)
index += 1
answer = max(answer, len(num_set)) # 최댓값 갱신
# 만약 처리시간이 끝났다면 다음 시간 구간에서 현재 처리 번호는 포함되지 않아야 하므로
# 다음 for loop가 돌기 전 세트에서 현재 처리 번호를 제거
if status == "end":
num_set.remove(num)
return answer
처음 문제를 풀 때에는 for loop 마지막에 다음과 같이 if 조건문이 존재하지 않았었다.
for index, (time, num, status) in enumerate(times):
while index < len(times) and times[index][0] < time + 1000:
next_time, next_num, next_status = times[index]
if next_num not in num_set:
num_set.add(next_num)
index += 1
answer = max(answer, len(num_set))
num_set.remove(num)
이 경우 2, 3, 18번 테스트 케이스를 통과하지 못하였고 코드의 오류를 알아채 if 조건문을 추가한 형태로 수정을 하였다. 수정한 결과가 code1
이며 2, 3, 18번 테스트 케이스도 통과할 수 있었다. 하지만 기존에 통과되던 7, 8, 9번 테스트 케이스를 code1
코드로는 통과하지 못하였고 코드의 오류 또한 파악하기 어려웠다.
status
를 판별하는 if 조건문 한 줄로 인해 통과하는 테스트 케이스가 달라지는 점을 바탕으로 다음과 같은 추측을 하였다.
status == "end"
조건을 만족하는 경우에만 num_set
에서 num
을 제거하는 경우 7, 8, 9번 테스트 케이스는 통과 못하지만 조건 없이 제거할 때에는 통과한다. status == "start"
인 경우에도 num_set
에서 num
이 제거되어야 7, 8, 9번 테스트 케이스를 통과할 수 있다. code1
에서는 동시에 벌어지는 처리의 경우 가장 먼저 탐색하는 처리에서만 올바르게 처리 갯수를 구할 수 있다.status == "end"
를 만족하므로 num_set.remove(num)
코드가 실행되고 따라서 이후 3번 처리나 5번 처리에서는 3초에 1번 처리가 끝났음을 알 수 없다.결론적으로, 처리가 같은 시각에 동시에 처리될 때에 status
의 처리가 어딘가에서 꼬인다고 생각하였고 고민 끝에 times
에 시각을 저장하는 데에서 문제가 발생한다는 것을 알게 되었다.
times
리스트에서 각 시각을 탐색할 때에는 시각이 오름차순 정렬되어 있다는 전제조건 뿐만 아니라, 시작 시각(start
)이 끝 시각(end
)보다 times
리스트에서 앞서 나와야 한다는 조건 또한 필요하다. 하지만 code
에서는 이를 놓쳐 times
리스트가 정렬될 때에 동일한 처리지만 끝 시각이 시작 시각보다 먼저 나오는, 다음과 같은 경우가 생긴다.
T == 0.001
make_pretty_time(end) - s * 1000 - ms + 1 == make_pretty_time(end)
times = [(make_pretty_time(end), num, "end"), (make_pretty_time(end), num, "start")]
따라서 같은 처리임에도 end
시각이 먼저 등장하여 이후 나오는 start
시각이 영원히 times
리스트에 제거되지 못하고 남게 되는 오류가 발생한다. 이를 해결하기 위해 알파벳 정렬을 고려하여 start
를 astart
로 변경하였고, 모든 테스트 케이스를 통과할 수 있었다.
리스트에 원하는 값을 이후 계산에 필요한 상태와 함께 튜플로 묶어 함께 저장하는 경우, 리스트 정렬시 상태 문자열도 함께 고려를 해야 한다. 특별한 조건이 없는 경우 문제가 되지 않지만 상태에도 순서가 부여되는 경우 상태 문자열에 따라 정렬 결과가 달라져 유의해야 한다.