[프로그래머스] 72412 순위검색 (2021 카카오 블라인드)

1. 문제

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

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

2. 접근방법

info 50000개 query 100000개

완탐 풀이하면 50000 * 100000 * 5

완탐 풀이로 하면 시간 복잡도가 슬퍼한다.

 

그렇기 때문에 각 값들을 잘 몰아넣고 해당되는 것만 뽑아보면 좋겠다 싶었다.

 

정보로 들어오는 값을

가능한 모든 경우의수로 쪼개서

각  경우의 수에 score를 저장하고

query에 해당하는 점수모음만 꺼내 그 안에서 조건에 해당하는 점수보다 높은 것의 갯수를 세면 된다.

 

구현은

HashMap을 이용해 key로 String, value로 List<Integer>를 준다.

Map에 저장 하는 것은

ex "java backend junior pizza 150"

의 경우

java에도 포함

java backend에도 포함

java junior에도 포함 ..... 되므로

 

입력으로 들어온 4가지 값의 조합을 구해

각 조합에 모두 150이란 값을 저장해주면 된다.

 

모든 조합을 구해 저장한다 해도 종류가 적어

2 ^ 4 * 50000 정도로 많은 시간을 필요로 하지 않는다.

 

이것을 뽑아 올 때는

필터에 사용 되는 값만 이어 붙여 key로 만든다.

ex) cpp and - and senior and pizza 250 -> cppseniorpizza

key에 저장된 점수들을 가져와 score보다 높은 점수의 갯수를 구하면 된다.

 

점수의 갯수를 셀 때도 완탐 시 시간 초과가 나니 정렬 후 이분탐색을 하여야 한다.

 

 

3. 자바 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class P72412순위검색 {

	Map<String, List<Integer>> map = new HashMap<String, List<Integer>>();
	
	public int[] solution(String[] info, String[] query) {
		for (String i : info) {
			String[] iSplit = i.split(" ");
			comb(iSplit, 0);
		}
		for (String key : map.keySet())
			Collections.sort(map.get(key));
		int[] answer = new int[query.length];
		for (int i = 0; i < query.length; i++) {
			String q = query[i];
			q = q.replace(" and", "");
			String[] qSplit = q.split(" ");
			String key = "";
			for (int j = 0; j < 4; j++)
				key += qSplit[j].equals("-") ? "" : qSplit[j];
			int score = Integer.parseInt(qSplit[4]);
			List<Integer> scoreList = map.getOrDefault(key, new ArrayList<Integer>());
			int s = 0;
			int l = scoreList.size();
			while (s < l) {
				int mid = (s + l) / 2;
				if (scoreList.get(mid) < score)
					s = mid + 1;
				else
					l = mid;
			}
			answer[i] = scoreList.size() - s;
		}
		return answer;
	}

	boolean selidx[] = new boolean[4];

	void comb(String[] iSplit, int idx) {
		if (idx == 4) {
			String s = "";
			for (int i = 0; i < 4; i++)
				s += selidx[i] ? iSplit[i] : "";
			map.put(s, map.getOrDefault(s, new ArrayList<Integer>()));
			map.get(s).add(Integer.parseInt(iSplit[4]));
			return;
		}
		selidx[idx] = true;
		comb(iSplit, idx + 1);
		selidx[idx] = false;
		comb(iSplit, idx + 1);
	}

}

4. 마치며

문제가 오우... 개념도 많이 필요하고 풀이 방법을 떠올리기도 굉장히 까다로운 문제였다.