[Programmers]17676. [1차] 추석 트래픽

17676. [1차] 추석 트래픽

❌ code1

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

시도

1. 시각은 밀리초를 기준으로 변환한다.
2. 1초 내에 일어나는 처리의 갯수는 처리의 시작 시각과 끝 시각에만 변동이 생긴다. 따라서 처리의 시작 시각과 끝 시각을 함께 리스트에 저장한다.
   1. 모든 처리에 대하여 시작 시각과 끝 시각을 times리스트에 변환하여 처리의 인덱스 번호, 처리의 시작 또는 끝 상태를 튜플로 함께 저장한다.
   2. 정확히는 끝 시각의 1 초 이후에 처리가 종료되어 처리 갯수 감소가 일어나지만 계산의 편의를 위해 끝 시각을 기준으로 잡는다.
3. times 리스트에 기록된 시각에 대하여 특정 시각(time)부터 1초 이내의 구간을 탐색한다. 탐색 중인 구간을 현재 구간이라 한다.
4. 현재 구간에 포함된 처리는 그 인덱스 번호를 기준 삼아 세트에 저장한다.
   1. 현재 구간에 포함된 처리는 시간 내에 시작되거나 끝이 난 처리(times[index][0] < time + 1000)이다.
   2. 조건을 만족하는 처리 번호를 num_set에 저장한다.
5. 세트에 저장된 처리의 갯수로 답을 갱신한다.
6. 만약 time에 이루어진 처리가 해당 처리의 종료를 의미한다면(status == "end") 다음 time에서는 이를 포함하지 않도록 num_set에서 제거한다.

문제

7, 8, 9번 테스트 케이스를 통과하지 못하였다.

⭕ code2

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 조건문 한 줄로 인해 통과하는 테스트 케이스가 달라지는 점을 바탕으로 다음과 같은 추측을 하였다.

1. status == "end" 조건을 만족하는 경우에만 num_set에서 num을 제거하는 경우 7, 8, 9번 테스트 케이스는 통과 못하지만 조건 없이 제거할 때에는 통과한다.
   1. 즉 status == "start"인 경우에도 num_set에서 num이 제거되어야 7, 8, 9번 테스트 케이스를 통과할 수 있다.
2. code1에서는 동시에 벌어지는 처리의 경우 가장 먼저 탐색하는 처리에서만 올바르게 처리 갯수를 구할 수 있다.
   1. 예를 들어 1번 처리가 3초에 끝나고 3번 처리는 3초에 시작되며 5번 처리도 3초에 시작하는 경우
      1. 1번 처리에서는 세 개의 처리가 동시에 벌어짐을 판단할 수 있다.
      2. 하지만 1번 처리는 status == "end"를 만족하므로 num_set.remove(num) 코드가 실행되고 따라서 이후 3번 처리나 5번 처리에서는 3초에 1번 처리가 끝났음을 알 수 없다.
      3. 하지만 답은 최댓값만 알면 되기 때문에 가장 먼저 탐색할 때만 옳은 답을 구하여도 무방하다.
   2. 답을 구하는 데에는 문제가 없다고 생각했었지만 계속 정답을 맞추지 못하기에 이 부분에서 오류가 발생할 확률이 높다.

결론적으로, 처리가 같은 시각에 동시에 처리될 때에 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로 변경하였고, 모든 테스트 케이스를 통과할 수 있었다.

요약

리스트에 원하는 값을 이후 계산에 필요한 상태와 함께 튜플로 묶어 함께 저장하는 경우, 리스트 정렬시 상태 문자열도 함께 고려를 해야 한다. 특별한 조건이 없는 경우 문제가 되지 않지만 상태에도 순서가 부여되는 경우 상태 문자열에 따라 정렬 결과가 달라져 유의해야 한다.