만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

래환이의 택시 타기 대작전

면접 대비

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

요약
N명 학생의 희망 출발 시각(HH:MM)을 바탕으로, 한 택시에 최대 3명을 태우고 출발 시각 차이가 10분 이내가 되도록 하는 택시 수의 최솟값을 구합니다.
난이도

쉬움10점 중 3점

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

문제

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

귀갓날 래환이는 벌칙 게임에서 져서 NN명 학생의 택시비를 내기로 했다. 돈이 없는 래환이는 필요한 택시 대수를 최소화하려 한다. 학생별로 원하는 귀가 시각이 주어질 때, 필요한 택시의 최소 대수를 구해 래환이를 도와주자.

입력

첫 번째 줄에 정수 NN (1≤N≤2×105)(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