카카오 블라인드 2021) 순위 검색

순위 검색

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

 

이 문제도 여러 시도를 통해 풀었다.

처음에 시도했던 것은, 문제의 조건에 따라 모두 파싱한 후, 값을 담을 class를 선언하여 인스턴스를 생성했었다. 이후, 각 조건들과 default인 조건에 따라 HashMap에 저장을 해주었는데, HashMap의 제네릭이 HashMap이고, 계속 타고 내려가다보니 로직이 복잡해졌었다.

더 좋은 방법이 없을까 고민하다가, 다른 분의 풀이를 보니 default인 경우와 주어진 경우를 조합해서 key값으로 저장하는 방법이었다.

 

문제에서 주어진 조건을 split한 이후, default를 포함한 경우를 for문을 통해 조합해주며 key 값을 만들어주었다.

이 때, 이중 반복문을 통해 값을 저장해주는데, 비트 연산을 통해 조건에 부합하는 key 값을 생성해서 넣어주었다. (default -는 공백으로 처리한다.)

 

모든 값을 조건에 따라 저장했으면, 해당 key에 들어있는 value를 오름차순으로 정렬해준다.

정렬 이후에는 각 쿼리에 해당하는 지원자들의 List를 받아와서, 몇 명이 조건에 부합하는지 구해주었다.

구할 때는 카카오의 힌트인 lower bound를 사용해서, 가장 처음으로 나오는 합격 최저 점수의 인덱스를 전체 길이에서 빼주어 구했다. (list의 size - lower bound 결과 인덱스)

 

저장할 때와, 소팅할 때, computeIfAbsent와 Entry를 사용해서 정렬할 수 있다는 것을 이 분의 풀이를 보고 내가 자바를 제대로 사용하지 못하고 있구나를 느꼈다.. 덕분에 자바에 대해 더 이해할 수 있었다.

 

코드

import java.util.*;

public class Solution {
  final String DEFAULT = "-", QUERY_REGEX = " and ", SPACE = " ", NOTHING = "";
  final int CONDITION_LENGTH = 4;
  final int SCORE_INDEX = 4;

  public int[] solution(String[] info, String[] query) {
    Map<String, List<Integer>> map = getInfoMap(info);
    int len = query.length;
    int[] answer = new int[len];

    for(int i=0; i<len; i++) {
      answer[i] = getCounts(map, query[i]);
    }

    return answer;
  }

  private Map<String, List<Integer>> getInfoMap(String[] info) {
    HashMap<String,List<Integer>> map = new HashMap<>();
    final int MAX_CONDITION = 1 << CONDITION_LENGTH;
    for(String applicant : info) {
      String[] data = getCondition(applicant);
      int score = Integer.parseInt(data[SCORE_INDEX]);

      for(int i=0; i<MAX_CONDITION; i++) {
        StringBuilder sb = new StringBuilder();
        for(int j=0; j<CONDITION_LENGTH; j++) {
          if((i&(1 <<j)) >0) { // i: 1 ~> j: 0, i: 2 ~> j: 1, i: 3 ~> j:0,1 , i: 4 ~> j: 1,2 
            sb.append(data[j]); // => 조합 가능한 모든 경우를 만들어 key로 생성
          }
        }
        String key = sb.toString();
        map.computeIfAbsent(key, mappingFunction -> new ArrayList<>()).add(score);
      }
    }

    for(Map.Entry<String, List<Integer>> entry : map.entrySet()) {
      entry.getValue().sort(null);
    }

    return map;
  }

  private int getCounts(Map<String, List<Integer>> map, String query) {
    String[] queryCondition = getCondition(query.replaceAll(DEFAULT, NOTHING).replaceAll(QUERY_REGEX, SPACE));
    String key = getKey(queryCondition);
    int score = Integer.parseInt(queryCondition[SCORE_INDEX]);
    List<Integer> list = map.getOrDefault(key, new ArrayList<>());

    return list.size() - lowerBound(list, score);
  }

  private String[] getCondition(String condition) {
    return condition.split(SPACE);
  }

  private String getKey(String[] conditions) {
    StringJoiner sj = new StringJoiner(NOTHING);
    for(int i=0; i<CONDITION_LENGTH; i++) {
      sj.add(conditions[i]);
    }
    return sj.toString();
  }

  private int lowerBound(List list, int score) {
    int left =0, right = list.size();

    while(left < right) {
      int mid = (left + right) /2;
      if((int)list.get(mid) >= score) {
        right = mid;
      } else {
        left = mid+1;
      }
    }
    return left;
  }
}

 

 

Reference

girawhale.tistory.com/94