G21276. 계보 복원가 호석

문제

제출 코드

• 사용 알고리즘 : 정렬, 자료구조

맵 3개, 리스트 1개, 배열 1개나 써 가면서 겨우 풀었음에도 모든 테케를 맞지 못한 문제.

개념 자체는 단순하다고 생각했는데, 구현하려니까 아무리 생각해도 최적화가 잘 되지 않았다.

내가 생각했던 이 문제의 핵심은, 모든 조상을 완벽하게 기억하고 있다는 점이었다.

각 사람들은, 자신의 부모와 그 조부모 등,, 연결된 모든 조상을 알고있다는 점 이다.

각 가문은 트리 형태를 이룬다고 했으므로, 본인에서 root까지 도달할때 지나가는 노드들을 모두 알고있다.

그 점을 이용해서, 각 사람별로 조상들을 따로 담아두고 조상들의 수가 가장 적은 사람부터 본인의 부모를 찾도록 했다.

뭔가 내가 복잡하게 풀었다는 걸 알고 있지만, 지금 당장은 더 봐도 다른 해답이 보이지 않아 추후 다시 풀고 모든 테케를 통과하는 풀이를 업로드 해야겠다.

package gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class G21276_translatorHoseok {

	static class Family implements Comparable<Family>{
		String child;
		List<String> parents; // child의 모든 조상들
		Family(String child){
			this.child = child;
			this.parents = new ArrayList<String>();
		}
		@Override
		public int compareTo(Family o) {
			return this.parents.size() - o.parents.size();
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		SortedMap<String, List<String>> childs = new TreeMap<String, List<String>>(); // 각 부모들의 자식 저장
		Map<String, Family> parents = new HashMap<String, Family>(); // 각 자식들의 조상들 저장

		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			String name = st.nextToken();
			childs.put(name, new ArrayList<String>());
			parents.put(name, new Family(name));
		}

		// 각 자식들에게 연결된 모든 조상들을 저장한다
		int M = Integer.parseInt(br.readLine());
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			String child = st.nextToken();
			String parent = st.nextToken();
			parents.get(child).parents.add(parent);
		}

		// 조상의 수가 적은 사람 우선으로 정렬
		Family[] parentsArr = parents.values().toArray(new Family[N]);
		Arrays.sort(parentsArr);

		int depth = 0, cnt = 0;
		Map<String, Integer> level = new HashMap<String, Integer>(); // 각 사람들의 레벨 저장

		List<String> roots = new ArrayList<String>();
		for(Family f : parentsArr) {
			depth = Math.max(depth, f.parents.size());

			for(String parent : f.parents) { // f.child의 모든 조상들
				if(!level.containsKey(parent)) { // 한번도 등장한 적 없는 부모
					level.put(parent, depth);
					if(depth == 1) roots.add(parent);
				}
				if(level.get(parent)==depth) { // f.child의 직계부모
					childs.get(parent).add(f.child);
				}
			}
		}

		StringBuilder sb = new StringBuilder();

		// 최상단 조상들 이름순 정렬 및 출력
		Collections.sort(roots);
		sb.append(roots.size() + "\n");
		for(String r : roots) sb.append(r + " ");
		sb.append("\n");

		// 각 사람들의 자식 출력
		for(String parent : childs.keySet()) {
			sb.append(parent + " " + childs.get(parent).size());
			Collections.sort(childs.get(parent)); // 자식들도 이름순 정렬 필요
			for(String child : childs.get(parent)) {
				sb.append(" " + child);
			}
			sb.append("\n");
		}

		System.out.println(sb);
	}

}