접근
이 문제는 사실 시간이 부족해서 조건문만 만족하도록 쿼리문을 만들다 보니
모든 테스트 케이스는 통과하지만 효율성 테스트에서 시간 초과가 발생하였습니다.
level2에저 정답률이 낮은 문제들을 보니 대부분
자료형에 대한 고려와 수학문제, 그리고 풀 수 있지만 효율성 테스트에서 실패하는 문제, 까다로운 조건들인 것 같습니다.
위 문제는 풀 수 있지만 효율성을 만족하지 못하는 문제에 해당됩니다.
제한사항을 보면
지원자는 1명이상 50,000명이하
그리고 개발부서의 조건은 1이상 100,000이하 입니다.
저의 경우 3중 for문을 만들어 풀었습니다.
각 조건이 모든 지원자들을 돌며 5가지 항목을 만족하는 개발자를 더하는 방식이었습니다.
하지만 위 방법은 시간 초과가 발생하는데
그 이유를 생각하면 각 조건이 모든 지원자를 돌면 안되는거 같습니다.
검색을 최소화할 수 있는 방법에 대해서 생각해봐야 하는데
시간이 부족해서 다른 사람분의 풀이를 참고하여 작성하겠습니다.
아래와 같은 흐름으로 풀이하였습니다.
- Map에 info가 조회될 수 있는 모든 경우의 수를 key로 넣고
info의 점수를 value로 넣는다. 단, Map의 value는 List의 형태이기 때문에 같은 key에 속하는 경우 list에 추가된다. - 1번 과정을 모든 지원자에 대해 마친 경우 각 key에 대해 value들을 정렬한다.
- 각 query에 해당하는 조건문이 map의 key에 존재하는지 확인하고 존재한다면 해당 key에 저장된 value를 이분탐색하여 query의 점수보다 작은 참가자들 중에서 가장 큰 참가자의 index를 반환한다.
- 조건에 맞는 응시자 수 = key에 해당하는 value의 개수 - 반환한 index
이분탐색에서 약간 헤매였습니다.
원래는 다음과 같이 이분탐색을 진행했습니다.
무엇이 문제인지 짐작가시나요?
바로 똑같은 점수가 여러개인 경우
즉 20[0] 30[1] 30[2] 30[3] 40[4] 일때
조건이 30점 이상의 참가자의 첫 위치를 구한다면
아래 이분탐색은 3번째 위치를 반환합니다.
static int search(String key , int score){
if(!map.containsKey(key)) return 0;
List<Integer> scoreList = map.get(key);
int l = 0;
int r = scoreList.size()-1;
int answer =0;
while(l<=r){
int mid = (l+r)/2;
if(scoreList.get(mid)>=score){
answer = mid;
r=mid-1;
}else{
l=mid+1;
}
}
return scoreList.size()-answer;
}따라서 이분탐색을 다음과 같이 고쳐주었습니다.
크거나 같은 것이 답이 되는 것이 아니라
작은 것들 중에서 가장 큰 수의 index를 구하도록 바꾸었습니다.
static int search(String key , int score){
if(!map.containsKey(key)) return 0;
List<Integer> scoreList = map.get(key);
int l = 0;
int r = scoreList.size()-1;
int answer =0;
while(l<=r){
int mid = (l+r)/2;
if(scoreList.get(mid)>=score){
r=mid-1;
}else{
l=mid+1;
}
}
return scoreList.size()-l;
}효율성 테스트 실패한 풀이
class Solution {
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
//1. 개발 언어 항목 cpp, java, python 중 하나
//2. 지원 직군 항목 front , back 중 하나
//3. 경력 구문 junior, senior 중 하나
//4. 소울푸드 chicken, pizza 중 하나
//[조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
// 지원자의 지원서 항목과 점수 info 1이상 50000이하 - 개발언어 직군 경력 소울푸드 점수( 1 이상 100,000)
// 궁금한 내용 query 1이상 100,000이하 개발언어 and 직군 and 경력 and - " cpp and - and senior and pizza 500"
//-> 각 조건에 해당하는 사람의 수를 return
// 지원자 나누고
String[][] inFo = new String[info.length][5];
for(int i=0;i<info.length;i++){
inFo[i]=info[i].split(" ");
}
// 조건 나누고
String[][] queRy = new String[query.length][5];
for(int i=0;i<query.length;i++){
String newQ = query[i].replace("and ","");
queRy[i]=newQ.split(" ");
}
for(int i=0;i<query.length;i++){
int cnt=0;
for(int j=0;j<inFo.length;j++){
boolean tag = false;
for(int z=0;z<4;z++){
if(queRy[i][z].equals("-")) continue;
if(!queRy[i][z].equals(inFo[j][z])){
tag=true;
break;
}
}
int qScore = Integer.parseInt(queRy[i][4]);
int iScore = Integer.parseInt(inFo[j][4]);
if(qScore>iScore) tag=true;
if(!tag) cnt++;
}
answer[i] =cnt;
}
return answer;
}
}성공한 풀이
import java.util.*;
class Solution {
static Map<String,List<Integer>> map = new HashMap<>();
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
//1. 개발 언어 항목 cpp, java, python 중 하나
//2. 지원 직군 항목 front , back 중 하나
//3. 경력 구문 junior, senior 중 하나
//4. 소울푸드 chicken, pizza 중 하나
//[조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
// 지원자의 지원서 항목과 점수 info 1이상 50000이하 - 개발언어 직군 경력 소울푸드 점수( 1 이상 100,000)
// 궁금한 내용 query 1이상 100,000이하 개발언어 and 직군 and 경력 and - " cpp and - and senior and pizza 500"
//-> 각 조건에 해당하는 사람의 수를 return
// 지원자 나누고
String[] inFo = new String[5];
for(int i=0;i<info.length;i++){
inFo=info[i].split(" ");
makeInfoMap(inFo,"",0);
}
//각 key에 대해 정렬하기
for(String key : map.keySet()){
Collections.sort(map.get(key));
}
//각 쿼리에 대해 조사하기
for(int i=0;i<query.length;i++){
String Q = query[i].replace(" and ","");
String[] q = Q.split(" ");
// System.out.println(q[0]);
//System.out.println(q[1]);
//검색하기
answer[i]=search(q[0],Integer.parseInt(q[1]));
}
return answer;
}
// 지원자에 대한 모든 경우의 수 만들기
static void makeInfoMap(String[] inFo,String key,int start){
if(start==4){
if(!map.containsKey(key)){
map.put(key,new ArrayList<Integer>());
}
map.get(key).add(Integer.parseInt(inFo[4]));
} else{
makeInfoMap(inFo,key+inFo[start],start+1);
makeInfoMap(inFo,key+"-",start+1);
}
}
// 이분탐색으로 해당하는 지원자 찾기
static int search(String key , int score){
if(!map.containsKey(key)) return 0;
List<Integer> scoreList = map.get(key);
int l = 0;
int r = scoreList.size()-1;
int answer =0;
while(l<=r){
int mid = (l+r)/2;
if(scoreList.get(mid)>=score){
r=mid-1;
}else{
l=mid+1;
}
}
return scoreList.size()-l;
}
}
꾸준하게 Ready, Set, Go!