[문제 설명]
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/72412
[문제 이해하기]
목적 : 개발팀들이 요구하는 지원자들이 몇명인지 파악하는 도구를 만드는 것.
도구 정보는 이러하다.
언어: cpp, java, python
직군: backend와 frontend
경력: junior와 senior
선호하는 소울 푸드 : chicken과 pizza
코딩테스트 점수 : X
파라미터정보
info 배열의 크기 1 이상 50,000 이하
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.(확인해야 될 내용)
query 배열의 크기는 1 이상 100,000 이하
1. "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.(확인해야될 내용)
2. '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.(확인해야될 내용)
3. X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
4. 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
문제를 읽어보고 내가 처음 구현한 방법
처음 배열의 크기를 고려하지 않고 구현했다 즉 query배열에서 info 배열을 찾는 방법으로 진행했다. 일단 여기서 시간초과 에러가 발생할것이다. O(50,000 * 100,000) 이므로
하지만 일단 구현해 보았다.
먼저 정답 배열은 answer의 크기는 개발팀수만큼 생성한다.
answer = new in[query.length]
info의 정보를 하나씩 꺼내 공백으로 분리여 각 배열에 담기로 했다.
ex) "java backend junior pizza 150" -> javabackendjuniorpizza150"
for(String que : query) {
for(String in :info) {
String str[] = in.split(" ");
// str[4] = 코딩테스트 점수가 될것이다.
}
}query 배열에서 and는 replaceAll(" and ","") 이러한 형태로 바라본다.
여기서 and를 바꾸는데 replaceAll 문법을 찾아 봤다.
내가 작성한 코드를 전체 살펴보면 이러하다
public class 순위검색 {
public static void main(String[] args) {
SolutionK6 m = new SolutionK6();
String[] info = {"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"};
String[] query = {"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"};
int answer[] = m.solution(info, query);
for(int num :answer) {
System.out.print(num+" ");
}
}
}
class SolutionK6 {
int answer[];
public int[] solution(String[] info, String[] query) {
answer = new int[query.length];
for(int i = 0; i < query.length; i++) {
String qu = query[i].replaceAll(" and "," ");
String test[] = qu.split(" ");
for(String in :info) {
String str[] = in.split(" ");
// str[4] = 코딩테스트 점수가 될것이다.
boolean flag = check(test,str);
if(flag) {
boolean flag2 = testcode(Integer.valueOf(test[4]),Integer.valueOf(str[4])); // 코딩 테스트 점수 확인
if(flag2) {
answer[i]++;
}
}
}
}
return answer;
}
private boolean testcode(Integer test, Integer str) {
if(test <= str) return true;
return false;
}
private boolean check(String[] test, String[] str) {
for(int i = 0; i <4; i++) {
if(test[i].equals("-")) continue;
if(!test[i].equals(str[i])) {
return false;
}
}
return true;
}
}실행결과 정답처리가 되었으나 효율성 문제에서 시간초과 에러 발생
이제 소스코드를 개선해보아야한다.
일단 2중 반복문을 사용해서는 안된다고 생각을 했다.
하지만 구현방법이 잘떠오르지 않아 다른분의 블로그를 참조하며 이해해보도록 노력했다.
참조한 블로그: https://jisunshine.tistory.com/153(감사합니다)
일단 map을 생성하여
info 배열의 원소를 하나씩 map에 저장한다.
*java backend junior pizza
java--- 150
-backend-- 150
--junior- 150
---pizza 150
--juniorpizza 150
:
javabackendjuniorpizza 150
java backend junior chicken 80
java--- [150,80]
-backend-- [150,80]
--junior- [150,80]
:
java backend junior chicken 80
info 배열하나씩 꺼내 각 조합들을 각각 map에 저장한다. 이때구현은 재귀함수로 구현한다.
depth를 코딩테스트 점수전까지인 4까지만 탐색을 한다.
그러면 위의 처럼 각각 저장이될것이다.
전체는 이러하다.
이상에서 map의 val값을 정렬한다. value값은 List 형이므로
Collections.sort()매서드를 이용했다.
이제 query배열을 순회하여 조건을 선택한다.
이때 구현한 것은 BinarySearch()라는 이분탐색 메서드를 구현했다.
BinarySearch()는 기본적으로 사전에 정렬이 되어있어야한다는 점이 있다.
메서드안 start,end변수를 생성후 mid을 만든다.
만약 mid번째 인덱스 값이 score(점수) 보다 낮은 면 mid+1것을 start로
mid번째 인덱스 값이 score(점수) 보다 높다면 mid-1을 end로
범위조건은 start<=end보다 작을때 까지 이다.
이렇게 구한값을 answer[]배열에 넣어 정답을 처리한다.
전체소스코드
import java.util.*;
class Solution {
int answer[];
HashMap<String,List<Integer>> map = new HashMap<>();
public int[] solution(String[] info, String[] query) {
answer = new int[query.length];
modifyedInfo(info); // info 수정
for(String key : map.keySet()){
Collections.sort(map.get(key)); // val 정렬
}
modifyedQuery(query); // query수정
return answer;
}
private void modifyedInfo(String[] info){
for(int i = 0; i<info.length; i++){
String str[] = info[i].split(" ");
// info 배열의 원소를 하나씩 저장
// java backend junior pizza
// java--- 150
// -backend-- 150
// --junior- 150
// ---pizza 150
// --juniorpizza 150
// :
// javabackendjuniorpizza 150
// java backend junior chicken 80
// java--- [150,80]
// -backend-- [150,80]
// --junior- [150,80]
// :
// java backend junior chicken 80
makeSetance(0,"",str); // 재귀함수 구현
}
}
private void modifyedQuery(String[] query){
// 완성된 map에서 query 살피기
for(int i = 0; i <query.length; i++){
query[i] = query[i].replaceAll(" and ",""); // "java and backend and junior and pizza 100"->"javabackendjuniorpizza 100"
String str[] = query[i].split(" ");
answer[i] = map.containsKey(str[0]) ? binarySearch(str[0],Integer.valueOf(str[1])) : 0;
}
}
public void makeSetance(int depth,String str,String info[]){
if(depth == 4){
if(!map.containsKey(str)){
List<Integer> list = new ArrayList<>();
map.put(str,list);
}
map.get(str).add(Integer.parseInt(info[4])); // 값을 추가
// ex) java--- = [150] -> java--- = [150,80] 80을 추가 작업
return;
}
// 2가지를 탐색
makeSetance(depth+1,str+"-",info);
makeSetance(depth+1,str+info[depth],info);
}
private int binarySearch(String str,int score){
List<Integer> list = map.get(str);
int start = 0; int end = list.size()-1;
while(start <= end){
int mid = (start+end)/2;
if(list.get(mid) < score){
start = mid + 1;
}else{
end = mid - 1;
}
}
return list.size() - start;
}
}
