문제링크
https://programmers.co.kr/learn/courses/30/lessons/72412
문제풀이ㅊㅊ👨🏻💻 핵심 스킬 👨🏻💻
구현, 이분탐색
1. 문제 이해
사용한 언어, 직군, 경력, 좋아하는 음식, 취득한 점수 5가지 칼럼으로 이루어진 데이터가 주어진다. 그리고 5개의 칼럼 중 점수를 제외한 4가지 칼럼에 조건 검색을 통해 사람들을 뽑아내고 그 사람들 중 취득한 점수가 x점 이상인 사람을 찾는 쿼리가 주어진다.
사람들의 정보 info와 query가 주어졌을 때 쿼리에 해당하는 사람의 수를 return해주는 문제이다.
이 때 쿼리에 '-'라는 문자가 올 수 있으며 '-'가 오는 경우에는 해당 조건을 통해 사람을 거르지 않는다는 것을 의미한다.
- 언어 : cpp, java, python
- 직군 : backend, frontend
- 경력 : junior, senior
- 좋아하는 음식 : chicken, pizza
2. 접근방법
1) info에 대한 정보를 Map을 만들어 데이터를 넣어준다.
- 이 때 Map에 들어가는 key는 쿼리를 value에는 해당 쿼리에 만족하는 사람들이 맞은 점수를 가지는 ArrayList로 넣어주었다.
- '-'에 대하여 처리해주기 위하여 '-'가 올 수 있는 모든 경우에 대하여 값을 넣어주었다.(총 16가지)
2) info에 대한 정보를 모두 넣은 map에 있는 ArrayList를 모두 오름차순으로 정렬한다.
- 추후 이분탐색을 위하여 오름차순으로 정렬해주었다.
3) 쿼리를 파싱하여 처리한다.
3. 구현코드 추가설명
String query = info.replaceAll("[0-9]", "");
query = query.trim();
int score = Integer.parseInt(info.replaceAll("[^0-9]", ""));
info에 대한 값을 처리하기 위해 필요한 문자들로 파싱하는 과정이다. query는 String만 남겨주고 score에는 숫자만 남겨준다.
String[] lang = {"-","-","-","-",splitInfo[0],splitInfo[0],splitInfo[0],splitInfo[0],"-","-","-",splitInfo[0],splitInfo[0],splitInfo[0],"-",splitInfo[0]};
String[] part = {"-","-","-",splitInfo[1],"-",splitInfo[1],"-","-",splitInfo[1],splitInfo[1],"-",splitInfo[1],splitInfo[1],"-",splitInfo[1],splitInfo[1]};
String[] career = {"-","-",splitInfo[2],"-","-","-",splitInfo[2],"-",splitInfo[2],"-",splitInfo[2],splitInfo[2],"-",splitInfo[2],splitInfo[2],splitInfo[2]};
String[] food = {"-",splitInfo[3],"-","-","-","-","-",splitInfo[3],"-",splitInfo[3],splitInfo[3],"-",splitInfo[3],splitInfo[3],splitInfo[3],splitInfo[3]};
info에 대한 정보를 넣어줄 때 만들어줄 수 있는 모든 값을 만드는 방법이다. 직접 하나하나 작성해주었다.
/**
* 이분탐색
*/
ArrayList<Integer> scores = db.get(key);
int left = 0;
int right = scores.size()-1;
int mid = 0;
while (right >= left){
mid = (right + left)/2;
if(scores.get(mid) >= score)
break;
left = mid + 1;
}
for(;mid != -1 && scores.get(mid) >= score; mid--);
return scores.size() - mid-1;
이분탐색을 수행해주는 코드이다. 쿼리로 주어지는 스코어의 값 이상을 찾아주는 것이기 때문에 조건에 맞는 큰 값을 먼저 찾아주고 그 조건을 만족하는 가장 작은 값이 있는 위치까지 옮겨주어야한다. 그 뒤 들어있는 데이터의 개수 전체에서 for문을 돌아 조건을 만족하는 가장 작은 값이 있는 위치의 값을 빼주면 원하는 값의 개수를 구할 수 있다.
구현코드
package pgm_72412;
import java.util.*;
public class Solution {
public Integer[] solution(String[] info, String[] query) {
ArrayList<Integer> answer = new ArrayList<>();
Map<String, ArrayList<Integer>> db = new HashMap<>();
processInfo(db, info);
sortDB(db);
for (String q : query)
answer.add(processQuery(db, q));
return answer.toArray(new Integer[0]);
}
/**
* DB에 List를 정렬
* @param db
*/
public void sortDB(Map<String, ArrayList<Integer>> db){
Set<String> keys = db.keySet();
for(String key : keys){
ArrayList<Integer> list = db.get(key);
list.sort(Comparator.naturalOrder());
db.put(key,list);
}
}
/**
* info에서 key와 score값을 추출하여 DB에 insert
* @param db
* @param infos
*/
public void processInfo(Map<String, ArrayList<Integer>> db, String[] infos) {
for (String info : infos) {
String query = info.replaceAll("[0-9]", "");
query = query.trim();
int score = Integer.parseInt(info.replaceAll("[^0-9]", ""));
insertDB(db,query,score);
}
}
/**
* db에서 insert되는 과정
* 이 때 key로 만들수 있는 16가지를 배열로 선언하여 삽입할 때 함께 삽입해줌.
* @param db
* @param info
* @param score
*/
public void insertDB(Map<String, ArrayList<Integer>> db, String info, int score){
String[] splitInfo = info.split(" ");
String[] lang = {"-","-","-","-",splitInfo[0],splitInfo[0],splitInfo[0],splitInfo[0],"-","-","-",splitInfo[0],splitInfo[0],splitInfo[0],"-",splitInfo[0]};
String[] part = {"-","-","-",splitInfo[1],"-",splitInfo[1],"-","-",splitInfo[1],splitInfo[1],"-",splitInfo[1],splitInfo[1],"-",splitInfo[1],splitInfo[1]};
String[] career = {"-","-",splitInfo[2],"-","-","-",splitInfo[2],"-",splitInfo[2],"-",splitInfo[2],splitInfo[2],"-",splitInfo[2],splitInfo[2],splitInfo[2]};
String[] food = {"-",splitInfo[3],"-","-","-","-","-",splitInfo[3],"-",splitInfo[3],splitInfo[3],"-",splitInfo[3],splitInfo[3],splitInfo[3],splitInfo[3]};
for(int i = 0; i < lang.length; i++){
String key = lang[i] + part[i] + career[i] + food[i];
ArrayList<Integer> list;
if (db.containsKey(key))
list = db.get(key);
else
list = new ArrayList<>();
list.add(score);
db.put(key, list);
}
}
/**
* Query를 처리하는 메소드
* @param db
* @param query
* @return
*/
public int processQuery(Map<String, ArrayList<Integer>> db, String query) {
String[] splitQuery = query.split(" and ");
String lang = splitQuery[0];
String part = splitQuery[1];
String career = splitQuery[2];
String food = splitQuery[3].split(" ")[0];
String key = lang + part + career + food;
int score = Integer.parseInt(query.replaceAll("[^0-9]", ""));
if(!db.containsKey(key))
return 0;
/**
* 이분탐색
*/
ArrayList<Integer> scores = db.get(key);
int left = 0;
int right = scores.size()-1;
int mid = 0;
while (right >= left){
mid = (right + left)/2;
if(scores.get(mid) >= score)
break;
left = mid + 1;
}
for(;mid != -1 && scores.get(mid) >= score; mid--);
return scores.size() - mid-1;
}
}
잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)
'CodingTest > Programmers' 카테고리의 다른 글
[PGM_76502] 괄호 회전하기 (java) (0) | 2022.03.08 |
---|---|
[PGM_42890] 후보키 (java) (0) | 2022.03.03 |
[PGM_12985] 예상 대진표 (java) (0) | 2022.02.28 |
[PGM_42577] 전화번호 목록 (java) (0) | 2022.02.27 |
[PGM_87946] 피로도 (java) (0) | 2022.02.26 |