문제 링크

문제 간단 해석

쿼리로 접근하여 원하는 사람의 명수를 얻어오는 문제. 처음 풀 때 '이게 2단계라고?'라는 생각이 마구 들었다.

Java

풀이 코드

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.StringJoiner;
import java.util.Comparator;

class Solution {
    public int[] solution(String[] info, String[] query) {
        Map<String, List<Integer>> map = new HashMap<>();
        String[] state;
        StringJoiner sj;
        String key;

        for (String user: info) {
            state = user.split(" ");

            for (int bit = 0; bit < (1 << 4); bit++) {
                sj = new StringJoiner(" ");

                for (int left = 0; left < 4; left++) {
                    if (((bit >> left) & 1) == 1)
                        sj.add(state[left]);
                    else
                        sj.add("-");
                }

                key = sj.toString();

                if (!map.containsKey(key))
                    map.put(key, new ArrayList<>());

                map.get(key).add(Integer.parseInt(state[4]));
            }
        }

        map.forEach((k, v) -> v.sort(Comparator.naturalOrder()));

        int[] answer = new int[query.length];
        List<Integer> list;
        int head, tail, target;

        for (int i = 0; i < query.length; i++) {
            state = query[i].split(" ");
            key = new StringJoiner(" ").add(state[0]).add(state[2]).add(state[4]).add(state[6]).toString();

            if (!map.containsKey(key))
                continue;

            list = map.get(key);
            head = 0;
            tail = list.size();
            target = Integer.parseInt(state[7]);

            while (head < tail) {
                if (list.get((head + tail) / 2) < target)
                    head = (head + tail) / 2 + 1;
                else
                    tail = (head + tail) / 2;
            }

            answer[i] = list.size() - head;
        }

        return answer;
    }
}

해석

for (String user: info) {
    state = user.split(" ");

    for (int bit = 0; bit < (1 << 4); bit++) {
        sj = new StringJoiner(" ");

        for (int left = 0; left < 4; left++) {
            if (((bit >> left) & 1) == 1)
                sj.add(state[left]);
            else
                sj.add("-");
        }

        key = sj.toString();

        if (!map.containsKey(key))
            map.put(key, new ArrayList<>());

        map.get(key).add(Integer.parseInt(state[4]));
    }
}

0000 ~ 1111까지 비트를 만드는데, 0인지 1인지에 따라 지원자들의 조건을 살릴지 말지 선택한다.
java backend junior pizza 150 지원자는

- - - -
- - - pizza
- - junior -
- - junior pizza
- backend - -
- backend - pizza
- backend junior -
- backend junior pizza
java - - -
java - - pizza
java - junior -
java - junior pizza
java backend - -
java backend - pizza
java backend junior -
java backend junior pizza

를 key로 두는 HashMap에 점수가 올라가게 된다.

map.forEach((k, v) -> v.sort(Comparator.naturalOrder()));

이분탐색을 위해, List들을 정렬한다.

for (int i = 0; i < query.length; i++) {
    state = query[i].split(" ");
    key = new StringJoiner(" ").add(state[0]).add(state[2]).add(state[4]).add(state[6]).toString();

    if (!map.containsKey(key))
        continue;

    list = map.get(key);
    head = 0;
    tail = list.size();
    target = Integer.parseInt(state[7]);

    while (head < tail) {
        if (list.get((head + tail) / 2) < target)
            head = (head + tail) / 2 + 1;
        else
            tail = (head + tail) / 2;
    }

    answer[i] = list.size() - head;
}

return answer;

쿼리로 key를 만들고, 해당 key에 맞는 데이터가 있다면 List를 가져온다.
List 내 값들 중 조건과 일치하지 않는 개수(찾는 점수보다 낮은 지원자)를 찾은 후 전체 지원자의 값에서 빼준다.

그 후 반환.

Python

풀이 코드

def solution(info, query):
    dic = {}
    
    for i in range(len(info)):
        info[i] = info[i].split()
        info[i][-1] = int(info[i][-1])
    
    info.sort(key=lambda x: x[-1])
    
    for ifo in info:
        for bit in range(1 << 4):
            qry = [ifo[i] if (bit >> i) & 1 else '-' for i in range(4)]
            try:
                dic[' and '.join(qry)].append(ifo[-1])
            except:
                dic[' and '.join(qry)] = [ifo[-1]]
            
    answer = []
    
    for qry in query:
        qry = qry.split()
        
        try:
            score = dic[' '.join(qry[:-1])]
        except KeyError:
            answer.append(0)
            continue
        
        limit = int(qry[-1])
        head = 0
        tail = len(score)
        
        while head != tail:
            if score[(head + tail) // 2] < limit:
                head = (head + tail) // 2 + 1
            else:
                tail = (head + tail) // 2
        
        answer.append(len(score) - head)
        
    return answer

해석

    for i in range(len(info)):
        info[i] = info[i].split()
        info[i][-1] = int(info[i][-1])
    
    info.sort(key=lambda x: x[-1])

처음부터 info의 마지막 값을 int로 형변환 후 정렬. 효율이 극대화된다.

for ifo in info:
    for bit in range(1 << 4):
        qry = [ifo[i] if (bit >> i) & 1 else '-' for i in range(4)]
        try:
            dic[' and '.join(qry)].append(ifo[-1])
        except:
            dic[' and '.join(qry)] = [ifo[-1]]

이 역시 bit가 1인지 0인지에 따라 조건을 살릴 지 말지 결정하여 key로 구성한다.

for qry in query:
    qry = qry.split()
    
    try:
        score = dic[' '.join(qry[:-1])]
    except KeyError:
        answer.append(0)
        continue
    
    limit = int(qry[-1])
    head = 0
    tail = len(score)
    
    while head != tail:
        if score[(head + tail) // 2] < limit:
            head = (head + tail) // 2 + 1
        else:
            tail = (head + tail) // 2
    
    answer.append(len(score) - head)
    
return answer

마지막 점수 항목을 뺀 나머지를 쿼리로 만들어, 점수가 적힌 리스트를 가져온다.
이분탐색으로 값을 찾고, answer에 추가.

여담

Python을 다룰 당시, 저 방법이 아니면 죄다 시간초과가 났던 것 같다.
Java는.. 괜찮네.
역시 언어 각각의 알고리즘 장단점이 있는 듯 하다.