2021 KaKao Blind - 순위검색

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

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

 

[문제]

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

[제한사항]

• info 배열의 크기는 1 이상 50,000 이하입니다.
• info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
  • 개발언어는 cpp, java, python 중 하나입니다.
  • 직군은 backend, frontend 중 하나입니다.
  • 경력은 junior, senior 중 하나입니다.
  • 소울푸드는 chicken, pizza 중 하나입니다.
  • 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
• query 배열의 크기는 1 이상 100,000 이하입니다.
• query의 각 문자열은 "[조건] X" 형식입니다.
  • [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
  • 언어는 cpp, java, python, - 중 하나입니다.
  • 직군은 backend, frontend, - 중 하나입니다.
  • 경력은 junior, senior, - 중 하나입니다.
  • 소울푸드는 chicken, pizza, - 중 하나입니다.
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
  • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
  • 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

 

입력

 

Info	query
"java backend junior pizza 150", "python frontend senior chicken 210", "python frontend senior chicken 150", "cpp backend senior pizza 260", "java backend junior chicken 80", "python backend senior chicken 50"	"java and backend and junior and pizza 100", "python and frontend and senior and chicken 200", "cpp and - and senior and pizza 250", "- and backend and senior and - 150", "- and - and - and chicken 100", "- and - and - and - 150"

출력 

[1,1,1,1,2,4]

 

풀이

Info 정보에 대한 모든 조합을 Map<String, List<Integer>>자료구조에 저장합니다. 첫번째 데이터를 예로들면 "java backend junior pizza 150"에서 나올 수 있는 조합은 총 16가지가 나옵니다.

 

	언어	직군	경력	소울푸드
1
2	java
3		backend
4			junior
5				pizza
6	java	backend
7	java		junior
8	java			pizza
9		backend	junior
10		backend		pizza
11			junior	pizza
12	java	backend	junior
13		backend	junior	pizza
14	java	backend		pizza
15	java		junior	pizza
16	java	backend	junior	pizza

 

16가지의 조합의 String을 Key 값으로, 점수를 Value 값으로 저장하며 이 때, 동일한 조합이 여러 번 반복될 수 있기 떄문에 List 형태로 점수를 저장합니다. Info 내 모든 데이터에 동일한 방법을 적용시킵니다. 조합을 구할 수 있는 방법은 재귀와 백트래킹 2가지 방법이 존재합니다. 저는 조합을 구할 때 재귀를 사용했습니다.

 

만약 백트래킹으로 풀고 싶으시다면 BOJ 사이트의 N과 M 문제를 풀어보시기 바랍니다.

 

N과 M 시리즈

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

모든 조합을 구했다면 모든 조합에 대한 점수 List를 오름차순으로 정렬합니다.(정렬하지 않으면 효율성 테스트를 통과할 수 없습니다.)

query에 존재하는 모든 데이터의 and와 - 를 제외한 나머지 String(점수 제외)을 구합니다. query에서 추출된 String을 Key에 해당하는 List를 구합니다.  List는 점수에 대해 오름차순으로 정렬했기 때문에 이분탐색 lowerbound 함수를 사용하여 쿼리에서 구하고자하는 점수 이상이 List의 index 값을 구합니다.

! lower bound 함수란 탐색값을 포함하여 시작되는 index 값을 구하는 함수입니다. lower bound와 upper bound 함수가 관련된 문제를 풀고 싶으시다면 BOJ 사이트의 숫자 카드2 문제를 풀어보시기 바랍니다.(upper bound 함수는 따로 설명하지 않겠습니다.)

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

마지막으로 (점수 List Size - index)를 구하면 문제에서 구하고자 하는 각 쿼리 점수를 info가 몇 개 존재하는지 알 수 있습니다.

 

코드

	public static int[] solution(String[] info, String[] query) {
		
		int[] answer = new int[query.length];
		store = new HashMap<>();
		
		for(int i=0;i<info.length;i++) {
			String[] temp = info[i].split(" ");
			boolean[] include = new boolean[temp.length];
			//재귀함수를 통해 Info에 대한 부분집합을 구함
			powerSet(temp, include, 0);					
		}
		
		//각 정보에 대한 부분집합에 해당되는 점수를 오름차순으로 정렬
		for(Entry<String, List<Integer>> entry : store.entrySet()) {
			Collections.sort(store.get(entry.getKey()));
		}
		
		for(int i=0;i<query.length;i++) {
			
			//조회 조건 convert
			int idx = query[i].lastIndexOf(" ");
			int score = Integer.valueOf(query[i].substring(idx+1));
			String inString = query[i].substring(0, idx).replace("and", "").replace(" ", "").replace("-", "");
			
			//조회 조건(점수 제외)에 맞는 점수 리스트 가져옴
			List<Integer> scores = store.get(inString);
			
			//1) lower bound를 이용해 특정 점수 이상에 해당하는 개수를 구함
			//전체개수 - 1)에서 구했던 개수를 통해 조건에 해당하는 개수를 구함
			if(!Objects.isNull(scores)) {
				int index = lowerBound(scores, 0, scores.size(), score);
				answer[i] = scores.size() - index;
			}
		}
		
		return answer;
	}
	
	public static void powerSet(String[] str, boolean[] include, int k) {
		
		if(k == str.length-1) {
			StringBuilder sb = new StringBuilder();
			
			for(int i=0;i<str.length-1;i++) {
				if(include[i]) {
					sb.append(str[i]);
				}
			}

			settingValue(sb.toString(), Integer.valueOf(str[str.length-1]));
			return;
		}

		include[k] = false;
		powerSet(str, include, k+1);
		include[k] = true;
		powerSet(str, include, k+1);						
	}
	
	public static void settingValue(String inString, int score) {

		if(!store.containsKey(inString)) {
			List<Integer> list = new ArrayList<>();
			list.add(score);
			store.put(inString, list);
		}
		else {
			store.get(inString).add(score);
		}	
	}
	
	public static int lowerBound(List<Integer> scores, int left, int right, int target) {
		
		int mid = 0;

		while(left < right) {
			mid = (left+right)/2;
			
			if(scores.get(mid) >= target) {
				right = mid;
			}
			else {
				left = mid+1;
			}
		}

		return right;
	}