문제
풀이
효율성 채점도 있는지 모르고 로직대로 완전탐색 구현했더니 효율성 0점이 나왔다!
내일 다시 보고 개선해보자!
(2021.03.25 추가)
지원자의 condition(언어, 포지션, 경력, 음식)을 조합한 모든 경우의 수에 대해 지원자의 점수를 Map으로 저장하고, 쿼리의 condition을 검색해서 점수리스트를 이분탐색하는 방식으로 구현했다. 물론 구글링을 해서 얻은 해법이다^^..
parseApplicantsInfo(): 주어진infos를 파싱해서testScoresPerCondition에 저장한다.
a.getCombinationOfInfo(): DFS로 조합을 구현해서, 가능한 모든condition을 List로 받는다.
b.addInfo(): 가능한 모든condition에 대해testScore을 Map에 추가한다.
c.applicants.sort(): 추후 이분 탐색을 위해 저장한testScoreList를 정렬해놓는다.query를 날릴 때마다 정렬하도록 했더니 시간초과가 떠서 여기서 한 번만 하도록 수정했다.queryForResults(): 주어진queries를 파싱해서queryResults에 저장한다.
a.parseTestScore():query에서 기준 점수값을 뽑아온다.
b.parseQueryIntoConditionString():query에서condition을 뽑아 전처리를 한 String으로 변환한다.
c.countAvailableApplicants():condition과testScore에 맞는 지원자 수를 센다.applicants를 이분 탐색하며testScore값의 lower bound index를 찾는다.
condition을 파싱할 때 공백(BLANK)를 하나하나 집어 넣어서 처리했었는데 그러면 자잘한 오류가 너무 많이 생기는 바람에 아예 공백을 모두 없애는 방식으로 수정했다. 애초에 그렇게 했다면 공간, 시간적으로 모두 더 효율적이었을텐데 미리 생각하지 못해서 아쉬웠다. 꼭 오류가 난 다음에야 그런 점들이 보이는게 참 아쉽다.
통과한 코드
import java.util.*;
class Solution {
private static final String BLANK = " ";
private static final String NULL = "";
private static final int LANGUAGE = 0;
private static final int POSITION = 1;
private static final int CAREER = 2;
private static final int SOUL_FOOD = 3;
private static final int TEST_SCORE = 4;
private static final int CONDITION_COUNT = 4;
private Map<String, List<Integer>> testScoresPerCondition = new HashMap<>();
private List<Integer> queryResults = new ArrayList<>();
public int[] solution(String[] infos, String[] queries) {
parseApplicantsInfo(infos);
queryForResults(queries);
return queryResults.stream().mapToInt(Integer::valueOf).toArray();
}
private void parseApplicantsInfo(String[] infos) {
for (String info : infos) {
String[] chunks = info.split(BLANK);
int testScore = Integer.parseInt(chunks[TEST_SCORE]);
List<String> conditions = getCombinationOfInfo(chunks);
for (String condition : conditions) addInfo(condition, testScore);
}
for (List<Integer> applicants : testScoresPerCondition.values()) applicants.sort(Integer::compareTo);
}
private List<String> getCombinationOfInfo(String[] chunks) {
List<String> result = new ArrayList<>();
for (int i = 0; i <= CONDITION_COUNT; i++)
dfs(new String[i], new boolean[CONDITION_COUNT], 0, 0, i, result, chunks);
return result;
}
private void dfs(String[] tmp, boolean[] visited, int start, int depth, int targetLength, List<String> result, String[] chunks) {
if (depth == targetLength) {
result.add(createConditionString(tmp));
return;
}
for (int i = start; i < CONDITION_COUNT; i++) {
if (!visited[i]) {
visited[i] = true;
tmp[depth] = chunks[i];
dfs(tmp, visited, i + 1, depth + 1, targetLength, result, chunks);
visited[i] = false;
tmp[depth] = BLANK;
}
}
}
private String createConditionString(String[] tmp) {
StringBuilder sb = new StringBuilder();
for (String str : tmp) sb.append(str);
return sb.toString().strip();
}
private void addInfo(String condition, int testScore) {
if (testScoresPerCondition.containsKey(condition)) {
testScoresPerCondition.get(condition).add(testScore);
} else {
List<Integer> testScores = new ArrayList<>();
testScores.add(testScore);
testScoresPerCondition.put(condition, testScores);
}
}
private void queryForResults(String[] queries) {
for (String query : queries) {
int testScore = parseTestScore(query);
String condition = parseQueryIntoConditionString(query.replace(Integer.toString(testScore), NULL));
if (!testScoresPerCondition.containsKey(condition))
queryResults.add(0);
else
queryResults.add(countAvailableApplicants(testScoresPerCondition.get(condition), testScore));
}
}
private int parseTestScore(String query) {
String[] chunks = query.split(BLANK);
return Integer.parseInt(chunks[chunks.length - 1]);
}
private String parseQueryIntoConditionString(String query) {
String[] chunks = query.replace("-", NULL).split("and");
return chunks[LANGUAGE].strip() + chunks[POSITION].strip()
+ chunks[CAREER].strip() + chunks[SOUL_FOOD].strip();
}
private int countAvailableApplicants(List<Integer> applicants, int testScore) {
int left = 0, right = applicants.size() - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (applicants.get(mid) < testScore) left = mid + 1;
else right = mid - 1;
}
return applicants.size() - left;
}
}효율성 0점 코드
import java.util.*;
class Solution {
private static final int LANGUAGE = 0;
private static final int POSITION = 1;
private static final int CAREER = 2;
private static final int SOUL_FOOD = 3;
private static final int TEST_SCORE = 4;
private Set<Applicant> applicants = new HashSet<>();
private List<Integer> queryResults = new ArrayList<>();
public int[] solution(String[] infos, String[] queries) {
parseApplicantsInfo(infos);
queryForResults(queries);
return queryResults.stream().mapToInt(Integer::valueOf).toArray();
}
private void parseApplicantsInfo(String[] infos) {
for (String info : infos) {
String[] chunks = info.split(" ");
applicants.add(new Applicant(new Condition(
chunks[LANGUAGE], chunks[POSITION], chunks[CAREER],
chunks[SOUL_FOOD], Integer.parseInt(chunks[TEST_SCORE]))));
}
}
private void queryForResults(String[] queries) {
for (String query : queries) {
Condition condition = parseQueryToCondition(query);
queryResults.add((int) applicants.stream()
.filter(applicant -> applicant.meetsCondition(condition))
.count());
}
}
private Condition parseQueryToCondition(String query) {
String[] conditions = query.split("and");
int testScore = parseTestScore(conditions[SOUL_FOOD].strip().split(" ")[1]);
String soulFood = conditions[SOUL_FOOD].strip().split(" ")[0];
return new Condition(conditions[LANGUAGE].strip(), conditions[POSITION].strip(),
conditions[CAREER].strip(), soulFood.strip(), testScore);
}
private int parseTestScore(String str) {
if (str.equals(Condition.NULL)) return Condition.NO_TEST_SCORE;
else return Integer.parseInt(str);
}
}
class Applicant {
Condition condition;
public Applicant(Condition condition) {
this.condition = condition;
}
public boolean meetsCondition(Condition condition) {
return this.condition.equals(condition);
}
}
class Condition {
static final int NO_TEST_SCORE = -1;
static final String NULL = "-";
String language;
String position;
String career;
String soulFood;
int testScore;
public Condition(String language, String position, String career, String soulFood, int testScore) {
this.language = language;
this.position = position;
this.career = career;
this.soulFood = soulFood;
this.testScore = testScore;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Condition)) return false;
Condition target = (Condition) o;
if (target.testScore != NO_TEST_SCORE && this.testScore < target.testScore) return false;
if (!target.language.equals(NULL) && !this.language.equals(target.language)) return false;
if (!target.position.equals(NULL) && !this.position.equals(target.position)) return false;
if (!target.career.equals(NULL) && !this.career.equals(target.career)) return false;
if (!target.soulFood.equals(NULL) && !this.soulFood.equals(target.soulFood)) return false;
return true;
}
@Override
public int hashCode() {
return Objects.hash(language, position, career, soulFood, testScore);
}
}