래환이의 택시 타기 대작전

시간 제한1초메모리 제한1024 MB

요약
N명의 희망 귀가 시각이 주어질 때, 각 학생이 원하는 시각의 10분 전후 안에 타도록 3인승 택시 대수를 최소로 구한다.
난이도

보통10점 중 5점

유형
그리디, 정렬, 투 포인터
정답자
아직 제출이 없습니다

문제

한과영 학생들은 귀가할 때 택시를 타고 부산역에 간다. 아쉽게도 캐리어 크기 때문에 하나의 택시에는 최대 33명의 학생만이 탑승할 수 있다. 또한 본인이 원하는 귀가 시각에서 1010분 전후 내로 택시를 탑승해야 한다. 단, 학생들은 모두 같은 날에 택시를 타야 한다.

하지만 귀갓날에 래환이는 벌칙에서 지는 바람에 NN명의 학생들의 택시비를 내기로 했고, 돈이 없는 래환이는 필요한 택시의 대수를 최소화하고 싶었다. 학생별로 본인이 원하는 귀가 시각이 주어질 때 필요한 택시의 최소 대수를 구해 래환이를 도와주자!

입력

첫 번째 줄에는 정수 N$$(1 \le N \le 2 \times 10^5)이 주어진다.

다음 NN개의 줄 중 ii번째 줄에 ii번째 학생이 원하는 귀가 시각이 주어진다. 시각은 HH:MM 형태로 주어지고, 00:00부터 23:59까지로 표현된다.

출력

학생들이 모두 택시를 타고 귀가하기 위해 필요한 택시의 최소 대수를 출력한다.

예제1

  1. 예제 1

    입력
    7
    16:30
    16:40
    17:37
    16:52
    17:30
    16:45
    17:40
    
    예상 출력
    3