쿼리로 접근하여 원하는 사람의 명수를 얻어오는 문제. 처음 풀 때 '이게 2단계라고?'라는 생각이 마구 들었다.
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 내 값들 중 조건과 일치하지 않는 개수(찾는 점수보다 낮은 지원자)를 찾은 후 전체 지원자의 값에서 빼준다.
그 후 반환.
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는.. 괜찮네.
역시 언어 각각의 알고리즘 장단점이 있는 듯 하다.