순위검색 - 프로그래머스 (Java, Level 2)

 

처음 풀이

간단한 문제라고 생각했다.

하나의 query마다, 모든 지원자들을 비교해가면서 몇 명이 해당하는지 셌다. 

 

solution()

public int[] solution(String[] info, String[] query) {
    int[] answer = new int[query.length];
    
    int index = 0;
    for (String conditions : query) {
        String[] condition = conditions.replaceAll("and ", "").split(" ");
        answer[index++] = find(condition[0],
                                condition[1],
                                condition[2],
                                condition[3],
                                condition[4],
                                info);
    }//for end

    return answer;
}//solution() end

 

find()

- 지원자 정보(info) 돌면서 query 조건에 맞는 사람 수 return하는 method

 

//info 돌면서 조건에 맞는 사람 찾는 method
public int find(String language,
                String department,
                String career,
                String food,
                String score,
                String[] info) {
    int count = 0;
    
    for (String participant : info) {
        String[] participantInfo = participant.split(" ");
        if ((language.equals("-") || participantInfo[0].equals(language))
        && (department.equals("-") || participantInfo[1].equals(department))
        && (career.equals("-") || participantInfo[2].equals(career))
        && (food.equals("-") || participantInfo[3].equals(food))
        && (Integer.parseInt(participantInfo[4])>=Integer.parseInt(score))) {
            count++;
        }
    }//for end

    return count;
}

 

 

정확성은 모두 맞았지만, 효율성에서 전부 틀렸다.

 

문제 시작할 때,

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

이런 문구가 괜히 있는 것이 아니었다. 

 

생각을 해보니 각 query마다 모든 지원자를 모두 비교하게 되면 최대 50,000 * 100,000회, 즉, 50억회 비교 연산이 이뤄져야 한다. 

 

중간중간 자잘한 수정으로는 효율성을 통과할 것 같지가 않다. 아예 풀이 방식을 새로 고민해야 한다.

 

 

개선 풀이(참고)

※ query를 직접 지원자와 일일이 비교하지 않는다.

 

- 지원자의 정보로부터, 지원자 정보가 포함될 수 있는 모든 query를 만들어서 이를 key로 하고 해당 key의 지원자의 점수들의 list를 value로 해서 map에 저장한다.

- 모든 지원자의 정보로 위 작업을 완료하면, 각 key에 대해 list를 오름차순 정렬한다.

- 주어진 각 query와 같은 key의 value list에서 해당 점수가 리스트에서 몇 번째인지 탐색한다.

 

makeStr()

- 지원자의 정보에서 "-"를 포함한 가능한 모든 query를 재귀적으로 만들어 점수와 함께 map에 저장하는 메소드

 

public void makeStr(int index, String[] condition, StringBuilder sb) {
    if (index==4) {
        //4가지 정보에 대한 query 모두 만들었으면
        String keyStr = sb.toString();
        //현재 keyStr에 해당하는 entry가 없으면 value에 들어갈 list 생성 후 map에 put
        if (!map.containsKey(keyStr)) {
            ArrayList<Integer> list = new ArrayList<>();
            map.put(keyStr, list);
        }
        //해당 list에 현재 지원자의 정보를 저장
        map.get(keyStr).add(Integer.parseInt(condition[4]));
        return;
    }

    //"-"포함한 query
    makeStr(index+1, condition, sb.append("-"));
    //sb에서 "-"제거
    sb.deleteCharAt(sb.length()-1);
    //현재 index에 해당하는 정보를 sb에 append
    makeStr(index+1, condition, sb.append(condition[index]));
    //현재 index에 해당하는 정보 sb에서 delete
    sb.delete(sb.length()-condition[index].length(), sb.length());
}

 

solution()

public int[] solution2(String[] info, String[] query) {
    map = new HashMap<>();

    for (String conditions : info) {
        //지원자마다 sb 초기화
        sb.setLength(0);
        //빈 칸을 기준으로 조건 split
        String[] condition = conditions.split(" ");
        //가능한 모든 query와 score를 map에 저장
        makeStr(0, condition, sb);
    }//for end

    //각 key에 해당하는 score list 오름차순 정리
    for (String key : map.keySet()) {
        Collections.sort(map.get(key));
    }//for end

    int answerSize = query.length;
    int[] answer = new int[answerSize];

    //주어진 각 query에서 해당하는 학생들 중 기준 점수 이상인 학생 수 저장
    for (int i = 0; i < answerSize; i++) {
        //query의 " and "를 ""롤 바꾼 후 빈 칸을 기준으로 split 한다.
        String[] queryInfo = query[i].replaceAll(" and ", "").split(" ");
        /**
         * queryInfo[0] : map의 key와 같은 query 형식
         * queryInfo[1] : 기준 점수
         */
        answer[i] = map.containsKey(queryInfo[0])? rank(queryInfo[0], Integer.parseInt(queryInfo[1])) : 0;
    }//for end

    return answer;
}

 

countAbove()

- 해당 query에서 기준 점수이상이 학생 수 return하는 method

 

public int countAbove(String key, int queryScore) {
    ArrayList<Integer> scores = map.get(key);
    int scoresSize = scores.size();

    for (int i = 0; i < scoresSize; i++) {
        if (scores.get(i)>=queryScore) {
            return scoresSize-i;
        }
    }//for end

    return 0;
}

 

 

여전히 효율성 테스트를 전부 통과하지는 못한다.

 

마지막 countAbove()에서 기준 점수가 몇 번째인지 찾는 탐색 과정을 선형탐색이 아닌 이분탐색으로 바꿨다.

 

 

countAbove() - 이분탐색

public int countAbove(String key, int queryScore) {
    ArrayList<Integer> scores = map.get(key);
    int scoresSize = scores.size();

    int start = 0;
    int end = scoresSize-1;

    while (start<=end) {
        int mid = (start+end)/2;

        if (queryScore<=scores.get(mid)) {
            end = mid-1;
        } else {
            start = mid+1;
        }
    }//while end

    return scoresSize-start;
}

 

 

전부 통과한 것을 확인할 수 있다.