[PGM_72412] 순위 검색 (java)

문제링크

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;

    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)