2021 - 순위 검색

https://programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

[ 문제풀이 ]

정확성과 효율성이 있는 문제이다. 해결법은 금방 찾았는데 조건문 하나를 빠뜨려서 계속해서 NullPointerException이 발생하는 바람에 구현하는데 생각보다 오래 걸렸다.

​나는 Trie 자료구조와 LowerBound 알고리즘을 이용해서 해결하였다.

​Trie 자료구조를 통해 ​개발언어, 직군, 경력, 소울푸드의 노드를 연결해 준 후 말단 노드에 점수들을 삽입한다.

​이후 query에서는 점수 A보다 크거나 같은 점수의 위치를 구해주면 빠르게 점수의 개수를 찾을 수 있기 때문에 LowerBound 알고리즘을 사용하여 해결하였다.

​

다른 풀이를 살펴보니 개발언어, 직군, 경력, 소울푸드의 개수가 굉장히 작기 때문에 굳이 Trie 자료구조로 관리할 필요가 없고 HashMap이나 배열로 관리해서 푸는 방법도 있었다.

HashMap<String, HashMap<String, HashMap<String, HashMap<String, ArrayList<Integer>>>>> langMap = new HashMap();
int[][][][][] map = new int[3][2][2][2][100001];

import java.util.*;

class Solution {
	Map<String, Integer> index;
	
	class Trie {
		Trie[] child;
		boolean flag = false; //리스트를 정렬했는지 체크
		List<Integer> scoreList;
		
		Trie () {
			child = new Trie[3];
		}
	}

	public void makeTrie(Trie root, int idx, String[] s) {
		//말단 노드는 점수들을 가지는 리스트를 가짐
		if (idx == 4) {
			if (root.scoreList == null) {
				root.scoreList = new ArrayList<>();
			}
			root.scoreList.add(Integer.parseInt(s[idx]));
			return;
		}
		
		int pos = index.get(s[idx]);

		if (root.child[pos] == null) {
			Trie child = new Trie();
			root.child[pos] = child;
		}

		makeTrie(root.child[pos], idx + 1, s);
	}

	public int query(Trie root, int idx, String[] q) {
		int answer = 0, pos = 0;
		
        //"-"가 2, 3, 두 가지 경우가 존재하기 때문에 예외로 처리
		if (q[idx].equals("-") && idx == 0) {
			pos = 3;
		} else {
			pos = index.get(q[idx]);
		}
		
		//개발언어, 직군, 경력은 계속해서 자식 노드를 탐색
		if (idx <= 2) {
			if (q[idx].equals("-")) {
				for (int i = 0; i < pos; ++i) {
					if (root.child[i] != null) {
						answer += query(root.child[i], idx + 1, q);
					}
				}
			} else {
				if (root.child[pos] != null) {
					answer += query(root.child[pos], idx + 1, q);
				}
			}
		} 
		//소울푸드는 자식 노드가 말단 노드이기 때문에 점수의 개수를 구해줌
		else {
			int key = Integer.parseInt(q[4]);
			
			if (pos <= 1) {
				if (root.child[pos] != null) {
					answer += lowerBound(root.child[pos], key);
				}
			} else {
				for (int i = 0; i < pos; ++i) {
					if (root.child[i] != null) {
						answer += lowerBound(root.child[i], key);
					}
				}
			}
		}

		return answer;
	}   

	//리스트에서 key보다 크거나 같은 원소의 위치를 찾는 함수
	public int lowerBound(Trie root, int key) {
		//리스트가 정렬되지 않았다면 lowerBound를 사용하기 위해 정렬
		if (!root.flag) {
			Collections.sort(root.scoreList);
			root.flag = true;
		}

		int left = 0, right = root.scoreList.size();

		while (left < right) {
			int mid = (left + right) / 2;

			if (root.scoreList.get(mid) < key) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		return root.scoreList.size() - right;
	}
	
	public String[] parsing(String query) {
		String[] q1 = query.split(" and ");
		String[] q2 = q1[3].split(" ");
		return new String[] {q1[0], q1[1], q1[2], q2[0], q2[1]};
	}
	
	public int[] solution(String[] info, String[] query) {
		index = new HashMap<>();
		index.put("cpp", 0); index.put("java", 1); index.put("python", 2);
		index.put("backend", 0);index.put("frontend", 1);
		index.put("junior", 0);index.put("senior", 1);
		index.put("chicken", 0);index.put("pizza", 1);
		index.put("-", 2);
				
		Trie root = new Trie();

		for (String str : info) {
			String[] s = str.split(" ");
			makeTrie(root, 0, s);
		}

		int[] answer = new int[query.length];
		for (int i = 0; i < query.length; ++i) {
			String[] q = parsing(query[i]);
			answer[i] = query(root, 0, q);
		}

		return answer;
	}
}