쇼핑몰 배포 전 의존성 점검

문제

한 온라인 쇼핑몰은 상품 검색, 주문 접수, 배송 조회 등 여러 기능을 별도의 서비스로 운영한다. 배포를 맡은 DevOps 담당자는 서비스가 사용하는 공통 모듈의 버전이 각 서비스의 요구 조건에 맞는지 확인해야 한다. 점검 도구가 모은 기록에는 현재 설치된 버전과 해당 서비스가 허용하는 버전 구간이 들어 있다. 기록은 입력된 순서대로 1번부터 번호를 붙인다. 이 쇼핑몰에서 사용하는 버전은 a.b.c 형식이다. a, b, c는 각각 0 이상 99 이하의 정수이며, 점 두 개로 구분한다. 각 정수는 값이 0인 경우를 제외하면 맨 앞에 0을 붙이지 않는다. 따라서 3.0.12는 올바른 표기이고 03.0.12는 올바른 표기가 아니다. 입력에는 이 규칙을 만족하는 버전만 주어진다. 두 버전의 크기는 세 정수를 왼쪽부터 비교하여 결정한다. 먼저 a를 비교하고, 같으면 b를 비교하며, 그것도 같으면 c를 비교한다. 처음으로 다른 위치의 정수가 큰 쪽이 더 높은 버전이다. 세 정수가 모두 같으면 같은 버전이다. 예를 들어 2.10.0은 2.9.99보다 높고, 3.0.0은 2.99.99보다 높다. 버전 전체를 일반적인 문자열의 사전 순서로 비교하지 않는다. 각 기록에는 설치 버전 V, 허용 하한 L, 허용 상한 U가 주어진다. 해당 기록의 요구 조건은 L ≤ V < U이다. 하한과 같은 버전은 사용할 수 있지만 상한과 같은 버전은 사용할 수 없다. 모든 기록에서 L < U가 보장되며, 서로 다른 기록의 허용 구간은 서로 관계가 없다. 담당자는 조건을 만족하지 않는 기록을 배포 검토 목록에 올리려 한다. 어떤 모듈을 업데이트하거나 다른 기록의 결과를 이용해 조건을 바꾸지는 않는다. 각 기록을 주어진 세 버전만으로 독립적으로 판단한다. 검토가 필요한 기록의 개수와 번호를 구하고, 번호는 작은 것부터 출력하는 프로그램을 작성한다.

입력

첫째 줄에 기록의 개수인 정수 N이 주어진다. 1 ≤ N ≤ 10,000이다.
다음 N개 줄에는 각각 설치 버전 V, 허용 하한 L, 허용 상한 U가 공백으로 구분되어 주어진다. 각 버전은 a.b.c 형식이며 a, b, c는 0 이상 99 이하의 정수다. 각 정수에는 불필요한 앞자리 0이 없다. 문제에서 정의한 버전 비교에 따라 모든 기록에서 L < U이다.

출력

첫째 줄에 요구 조건을 만족하지 않는 기록의 개수 K를 출력한다. K가 양수이면 둘째 줄에 해당 기록의 번호 K개를 오름차순으로 공백으로 구분하여 출력한다. K가 0이면 첫째 줄에 0만 출력하고 둘째 줄은 출력하지 않는다.

5
2.10.0 2.9.0 3.0.0
1.4.2 1.4.2 1.5.0
4.0.0 3.2.0 4.0.0
0.9.8 0.10.0 1.0.0
7.2.1 7.0.0 7.2.2

2
3 4

3
0.0.0 0.0.0 0.0.1
9.10.4 9.9.99 9.11.0
99.99.98 99.99.97 99.99.99

0

2
6.3.0 6.3.1 6.4.0
8.0.1 7.99.99 8.0.1

2
1 2

출처: Devin.KR 자체 제작