[프로그래머스] 순위 검색

2021 KAKAO BLIND RECRUITMENT 순위 검색

 

 

문제 

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

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

 

제출 코드 (텍스트는 맨 아래에)

전체 구성

 

 

 

메소드들

 

 

 

 

 

텍스트

import java.util.ArrayList;
import java.util.HashMap;

class Solution {
    //경우의 수 다 만들어서 찾자
    private final String[] language = {"cpp", "java", "python", "-"};
    private final String[] type = {"backend", "frontend", "-"};
    private final String[] career = {"junior", "senior", "-"};
    private final String[] food = {"chicken", "pizza", "-"};

    private final String wc = "-";  //wildCard

    public int[] solution(String[] info, String[] query) {
        int[] answer;
        ArrayList<Integer> answerList = new ArrayList<>();

        // db 초기화
        HashMap<String, ArrayList<Integer>> db = new HashMap<>();
        setDb(db);

        // score 입력
        for (String oneInfo : info)
            putScore(db, oneInfo.split(" "));

        // score 오름차순으로 정렬
        for (ArrayList<Integer> scoreList : db.values())
            scoreList.sort((o1, o2) -> o1 - o2);

        // 쿼리에 해당하는 인원수 체크
        for (String oneQuery : query)
            answerList.add(getCnt(db, oneQuery.replaceAll(" and", "").split(" ")));

        // ArrayList -> array
        answer = new int[answerList.size()];
        for (int i = 0; i < answerList.size(); ++i)
            answer[i] = answerList.get(i);

        return answer;
    }

    /**
     * 쿼리에 해당하는 인원 수 세어보자
     */
    private int getCnt(HashMap<String, ArrayList<Integer>> db, String[] oneQuery) {
        String key = oneQuery[0] + oneQuery[1] + oneQuery[2] + oneQuery[3];
        int score = Integer.parseInt(oneQuery[4]);
        int firstIdx = getFirstIdx(db.get(key), score);
        if (firstIdx >= 0) {
            return db.get(key).size() - firstIdx;
        }
        return 0;
    }

    /**
     * score 가 처음 등장하는 idx 찾기
     * 없으면 -1 리턴
     */
    private int getFirstIdx(ArrayList<Integer> list, int score) {
//        return Collections.binarySearch(list, score);
        int idx = list.size() / 2;
        int up = list.size() - 1;
        int down = 0;

        if (list.size() == 0) return -1;

        while (true) {
            if (up - down <= 1) {
                if (list.get(down) >= score) return down;
                if (list.get(up) >= score) return up;
                return -1;
            }
            if (list.get(idx) >= score) {
                up = idx;
            } else {
                down = idx;
            }
            idx = (down + up) / 2;
        }
    }

    /**
     * info 하나 받고, 모든 조건의 key 에 값 넣기
     */
    private void putScore(HashMap<String, ArrayList<Integer>> db, String[] oneInfo) {
        //0개
        db.get(oneInfo[0] + oneInfo[1] + oneInfo[2] + oneInfo[3]).add(Integer.parseInt(oneInfo[4]));

        //1개
        db.get(wc + oneInfo[1] + oneInfo[2] + oneInfo[3]).add(Integer.parseInt(oneInfo[4]));
        db.get(oneInfo[0] + wc + oneInfo[2] + oneInfo[3]).add(Integer.parseInt(oneInfo[4]));
        db.get(oneInfo[0] + oneInfo[1] + wc + oneInfo[3]).add(Integer.parseInt(oneInfo[4]));
        db.get(oneInfo[0] + oneInfo[1] + oneInfo[2] + wc).add(Integer.parseInt(oneInfo[4]));

        //2개
        db.get(wc + wc + oneInfo[2] + oneInfo[3]).add(Integer.parseInt(oneInfo[4]));
        db.get(wc + oneInfo[1] + wc + oneInfo[3]).add(Integer.parseInt(oneInfo[4]));
        db.get(wc + oneInfo[1] + oneInfo[2] + wc).add(Integer.parseInt(oneInfo[4]));
        db.get(oneInfo[0] + wc + wc + oneInfo[3]).add(Integer.parseInt(oneInfo[4]));
        db.get(oneInfo[0] + wc + oneInfo[2] + wc).add(Integer.parseInt(oneInfo[4]));
        db.get(oneInfo[0] + oneInfo[1] + wc + wc).add(Integer.parseInt(oneInfo[4]));

        //3개
        db.get(oneInfo[0] + wc + wc + wc).add(Integer.parseInt(oneInfo[4]));
        db.get(wc + oneInfo[1] + wc + wc).add(Integer.parseInt(oneInfo[4]));
        db.get(wc + wc + oneInfo[2] + wc).add(Integer.parseInt(oneInfo[4]));
        db.get(wc + wc + wc + oneInfo[3]).add(Integer.parseInt(oneInfo[4]));

        //4개
        db.get(wc + wc + wc + wc).add(Integer.parseInt(oneInfo[4]));
    }

    /**
     * 모든 경우의 수 set
     * 4 3 3 3
     */
    private void setDb(HashMap<String, ArrayList<Integer>> db) {
        for (String a : language)
            for (String b : type)
                for (String c : career)
                    for (String d : food)
                        db.put(a + b + c + d, new ArrayList<>());
    }
}