프로그래머스 순위 검색 (JAVA)

2021 KAKAO BLIND RECRUITMENT

순위 검색

 

Map을 사용한다는 발상 자체는 어렵지 않았으나, 효율성 부분이 이분탐색을 사용해야 통과되는 문제였고, 그 부분에서 시간초과가 날 줄 몰라서 당황하게 만들었던 문제였다.

 

1. 주어지는 문자열을 만능 문자인 '-'를 포함하여 만들어질 수 있는 모든 경우의 수로 추가한다

for (String s : info) {
      st = new StringTokenizer(s);
      String[] values = new String[4];
      values[0] = st.nextToken();
      values[1] = st.nextToken();
      values[2] = st.nextToken();
      values[3] = st.nextToken();
      int score = Integer.parseInt(st.nextToken());
      solve(0, values, score);
}

private static void solve(int pos, String[] values, int score) {
      if (pos == 4) {
          map.merge(values[0] + values[1] + values[2] + values[3], new ArrayList<Integer>(Arrays.asList(score)),
          (ori, init) -> {
                ori.add(score);
                return ori;
          });
          return;
      }
      String tmp = values[pos];
      solve(pos + 1, values, score);
      values[pos] = "-";
      solve(pos + 1, values, score);
      values[pos] = tmp;
}

2. 각 map의 value값들인 list를 오름차순으로 정렬한다.

for (List<Integer> list : map.values()) {
    Collections.sort(list);
}

 

3. 이분탐색을 활용하여 현재 내 점수보다 큰 점수들의 개수를 구한다.

for (String s : query) {
    String[] values = new String[4];
    st = new StringTokenizer(s);
    for (int i = 0; i < 7; i++) {
        if (i % 2 != 0) {
                st.nextToken();
                continue;
        }
    	values[i / 2] = st.nextToken();
    }
    int score = Integer.parseInt(st.nextToken());
    String str = values[0] + values[1] + values[2] + values[3];
    if (!map.containsKey(str)) {
        index++;
        continue;
    }
    List<Integer> list = map.get(str);
    int start = 0;
    int end = list.size() - 1;
    while (start <= end) {
      int mid = (start + end) / 2;
      if (list.get(mid) < score) {
      	start = mid + 1;
      } else {
      	end = mid - 1;
      }
    }
    result[index++] += list.size() - start;
}