Junior
면접 대비시간 제한2초메모리 제한512 MB
출생 순으로 주어지는 이름에서 junior나 iii를 붙인 이름과 중간 이름 규칙으로 부모 후보를 찾아 부모가 없는 사람 수를 구한다.
문제
여러 문화권에서 자녀는 부모 중 적어도 한 명과 성을 공유한다. 또한 적지 않은 가정에서 자녀에게 중간 이름을 붙여 조상, 흔히 조부모나 부모를 기린다. 어떤 경우에는 부모가 한 걸음 더 나아가 자녀에게 자신의 이름(first name)을 그대로 붙이기도 한다. 대개 아버지의 이름을 물려받는 첫째 아들이 이런 경우이며, 이때 두 사람을 구분하려고 이름 뒤에 "junior"를 붙인다. 이 문제에서는 이런 작명 관습을 이용해 주어진 데이터에 몇 개의 가족이 들어 있는지 판별한다.
이름 목록이 주어진다. 각 이름은 소문자와 공백으로만 이루어진 문자열이며, 공백은 이름의 각 부분을 구분한다. 이름은 이름(first name, 항상 존재), 중간 이름(middle name, 선택적), 성(last name, 항상 존재), 그리고 "junior" 또는 "iii" 중 하나(선택적)로 구성된다. 이름, 중간 이름, 성이 "junior" 또는 "iii"인 사람은 없다. 다음 두 조건을 만족하면 A가 B의 자녀라고 추론할 수 있다: (1) A가 B보다 나중에 태어났고, (2) 다음 중 하나가 성립한다.
- A의 이름이 B의 이름과 정확히 같고 뒤에 "junior"가 붙어 있다.
- A의 이름이 B의 이름과 같지만 "junior"가 "iii"로 바뀌어 있다. 즉, B의 이름은 "junior"로 끝나고 A의 이름은 "iii"로 끝나며, 그 부분을 제외하면 두 이름이 정확히 같다.
- A와 B의 성이 같고, A의 중간 이름이 B의 이름이며, A의 이름에 "junior"나 "iii"가 붙어 있지 않다.
데이터에 있는 가족의 수는 데이터에서 부모가 될 수 있는 사람을 찾지 못한 사람의 수다. (따라서 "fitzgerald kennedy"가 두 명, "john fitzgerald kennedy"가 한 명 있다면, 그가 어느 가족에 속하는지 알 수 없어도 상관없다.)
입력
첫 줄에는 파일에 있는 데이터 세트의 수 K ≥ 1이 주어진다. 그 뒤에 K개의 데이터 세트가 다음 형식으로 이어진다.
데이터 세트의 첫 줄에는 데이터에 있는 사람 수 1 ≤ n ≤ 1000이 주어진다. 그 뒤에 n개의 줄이 이어지며, 각 줄에는 길이가 최대 80자인 소문자와 공백으로만 이루어진 문자열이 하나씩 주어진다. 이름은 사람이 태어난 순서대로 주어진다.
출력
각 데이터 세트마다 먼저 "Data Set x:"를 한 줄에 출력한다. 여기서 x는 데이터 세트의 번호다. 그다음 데이터에 들어 있는 가족의 수, 즉 부모가 데이터에 있는지 알려지지 않은 사람의 수를 출력한다.
각 데이터 세트의 출력 뒤에는 빈 줄을 하나 출력한다.