수족관 제어기 배포 점검

문제

수족관의 운영 서버는 수온계, 조명 장치, 순환 펌프를 연결하는 여러 어댑터를 관리한다. DevOps 담당자는 공통 제어기를 새 버전으로 배포하기 전에 각 어댑터가 해당 버전에 의존할 수 있는지 점검한다. 이번 점검에서는 어댑터끼리의 연결 관계는 고려하지 않고, 각 어댑터가 선언한 제어기 버전 범위만 확인한다. 버전은 A.B.C 형식으로 표시한다. A, B, C는 각각 0 이상 99 이하의 정수다. 버전을 비교할 때는 먼저 A를 비교하고, A가 같으면 B를 비교하며, A와 B가 모두 같으면 C를 비교한다. 처음으로 값이 다른 성분에서 정수가 큰 쪽이 더 높은 버전이다. 세 성분이 모두 같으면 같은 버전이다. 따라서 버전 문자열 자체의 사전순으로 비교해서는 안 된다. 각 어댑터에는 허용하는 제어기 버전의 하한 L과 상한 U가 기록되어 있다. 배포할 버전을 V라고 할 때 L 이상이고 U 미만인 버전만 허용한다. 하한과 같은 버전은 허용하지만 상한과 같은 버전은 허용하지 않는다. 모든 어댑터의 하한은 상한보다 낮게 주어진다. 허용 범위를 벗어난 어댑터는 배포 전에 검토해야 하는 대상으로 분류한다. 어댑터에는 입력 순서대로 1번부터 N번까지 번호를 붙인다. 담당자는 검토 대상을 하한 버전이 낮은 순서대로 확인하려 한다. 하한 버전이 같은 대상이 여러 개라면 번호가 작은 것을 먼저 확인한다. 상한 버전은 검토 순서를 정하는 데 사용하지 않는다. 검토 대상의 수와 이 규칙에 따른 번호 목록을 구해야 한다. 모든 어댑터가 배포 버전을 허용한다면 검토 대상은 없으며, 이 경우에는 대상의 수 0만 보고한다.

입력

첫째 줄에 어댑터 수 N이 주어진다. N은 1 이상 12,000 이하의 정수다. 둘째 줄에 배포할 제어기 버전 V가 주어진다. 다음 N개 줄에는 각 어댑터의 하한 L과 상한 U가 공백으로 구분되어 주어진다. 모든 버전은 A.B.C 형식이며 각 성분은 0 이상 99 이하의 정수다. 각 성분에는 불필요한 앞자리 0이나 부호가 없다. 모든 범위에서 L < U가 성립한다.

출력

첫째 줄에 검토 대상의 수 K를 출력한다. K가 양수라면 둘째 줄에 하한 버전이 낮은 순서대로 대상의 번호를 공백으로 구분하여 출력한다. 하한이 같으면 번호가 작은 것을 먼저 출력한다. K가 0이면 첫째 줄만 출력한다.

4
2.10.0
2.9.0 2.11.0
2.10.0 3.0.0
1.0.0 2.10.0
3.0.0 4.0.0

2
3 4

2
0.0.0
0.0.0 0.0.1
0.0.0 99.99.99

0

3
1.0.0
2.0.0 3.0.0
0.0.0 1.0.0
2.0.0 2.0.1

3
2 1 3

출처: Devin.KR 자체 제작