위 문제는 Map에 List를 추가하는 새로운 방식의 유형이다.
Map의 Value값에 new ArrayList 하는 부분만 우선 참고하기 위해 서두에 올려놓겠다.
먼저 map.put(Key, new ArrayList<>())하는 부분이 하이라이트다.
Map<String, List<Integer>> map = new HashMap<>();
map.putIfAbsent(sb.toString(), new ArrayList<>());//ArrayList일단 틀 만들어놓기
map.get(sb.toString()).add(v);//value에 코테점수를 Arraylist .addget을 이용하여 ArrayList를 불러오고, 해당 ArrayList에 추가해주는 방식이면 Map의 중복불가한 특징을 보완할 수 있다.
필자는 효율성테스트에서 실패했다.
nuller를 이용해서 해보려고했지만 실패하였다.
class Solution {
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
String[][] people = new String[info.length][5];
String[][] condition = new String[query.length][5];
String[] lang = {"cpp", "java", "python"};
String[] job = {"backend", "frontend"};
String[] exp = {"junior", "senior"};
String[] food = {"chicken", "pizza"};
int i = 0;
for (String s : info) {
String[] arr = s.split(" ");
for (int j = 0; j < arr.length; j++) {
people[i][j] = arr[j];
}
i++;
}
for (int q = 0; q < query.length; q++) {
//쿼리값 테이블
String[] temp = query[q].split(" and ");
for (int t = 0; t < 3; t++) condition[q][t] = temp[t];
String[] temp2 = temp[3].split(" ");
condition[q][3] = temp2[0];
condition[q][4] = temp2[1];
//완성
//비교 시작
int count = 0;
for (String[] val : people) {
//동일하거나 상관없음이면 넘어가
if ((val[0].equals(condition[q][0]) || condition[q][0].equals("-"))
&& (val[1].equals(condition[q][1]) || condition[q][1].equals("-"))
&& (val[2].equals(condition[q][2]) || condition[q][2].equals("-"))
&& (val[3].equals(condition[q][3]) || condition[q][3].equals("-"))
&& (Integer.parseInt(val[4]) >= Integer.parseInt(condition[q][4]))) count++;
answer[q] = count;
}
}
return answer;
}
}
StringBuilder사용에 미숙하여 자꾸 nullpointer error가 떠서 모두 배열로 나눠서 비교를 했더니 역시나 효율성면에서 문제가 발생하였다.
풀이방향 출처:
tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/
2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설
지난 2020년 9월 12일 토요일 오후 2시부터 7시까지 5시간 동안 2021 카카오 신입 개발자 공채 1차 코딩 테스트가 진행되었습니다. 테스트에는 총 7개의 문제가 출제되었으며, 개발 언어는 C++, Java, Jav
tech.kakao.com
예를 들어, “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 됩니다.
| java | backend | junior | pizza | 150 |
| – | backend | junior | pizza | 150 |
| java | – | junior | pizza | 150 |
| java | backend | – | pizza | 150 |
| java | backend | junior | – | 150 |
| – | – | junior | pizza | 150 |
| – | backend | – | pizza | 150 |
| … (생략) | ||||
| java | – | – | – | 150 |
| – | – | – | – | 150 |
검색 조건이 “java and backend and junior and pizza 100″이라 하면, 위 지원자는 검색 대상에 포함되며, 검색 조건이 “java and – and junior and – 100” 인 경우에도 검색 대상에 포함이 됩니다.
따라서 모든 지원자들을 위와 같은 방식으로 분류한 후 같은 그룹의 지원자끼리 묶어두고, 해당 그룹에서 점수를 기준으로 오름차순 정렬해 둡니다.
이제, 검색 조건이 주어질 경우 INFO 배열에서 지원자들을 찾지 않고, 미리 분류해둔 그룹에서 X점 이상 맞은 지원자 수를 세주기만 하면 됩니다.
이때, X점 이상 맞은 지원자를 찾기 위해 해당 그룹의 최저점, 혹은 최고점부터 순차적으로 검색한다면 여전히 오랜 시간이 걸리게 됩니다.
이때, 숫자가 오름차순으로 정렬된 배열에서 X라는 숫자를 찾는 효율적인 방법으로 binary search를 사용할 수 있습니다. 이때, 배열에 X가 없을 수도 있으므로, 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 하며, 이는 lower bound를 이용하면 됩니다.
풀이
아마 2021년도는 조합(convolution)을 이용하는 문제가 트랜드인 듯하다.
코드는 아래에서 다시 설명하도록 하고 먼저 카카오에서 제시한 풀이방법을 뇌로 이해를 해보자.
필자는 Map에다가 그룹 지원자끼리 묶어놓는다는게 무슨의미인지 이해하지못했었다. 4중 Map으로 사용하는 코드는 당최 무슨 뜻인지 이해가 안됐다.
우리가 작성해야 될 코드 순서를 정리하자면
(String 분류하는 작업은 당연한 것이다.)
- info(지원자들 내용)를 Map<스펙(String),점수(Integer)>로 집어넣는것이다.
- 단, 동일스펙(String)의 지원자가 있을 수 있으므로 각각의 지원자 점수(Integer)를 List로 만든다.
- query(채용스펙)을 분류한다.
- 단, 채용스펙에서 상관없음("-") 인 사항에 대하여, DFS와 같은 방법으로 각각 카운팅한다.
이를테면, 지원자가 아래와 같은 스펙 4명인 경우
| java | pizza | 200 |
| java | chicken | 150 |
| python | pizza | 100 |
| python | pizza | 200 |
qeury에서 " - and pizza 150"을 구할때,
- java and pizza
- python and pizza
위 두가지 모두의 경우를 더해서 1명(java,1행)+ 1명(python,4행) = 2가지가 나온다.
따라서 DFS 방식으로 " - "부분을 재귀로 돌려서 최종적인 String Key(채용스팩)에 대하여 List에 접근하여 각각 값을 더해주면 되는것이다.
한가지 마지막으로 남았다. 효율성을 위하여 List의 코테점수값들은 모두 정렬되어있어야 한다.
| java | pizza | 200 |
| java | chicken | 150 |
| python | pizza | 100 |
| python | pizza | 200 |
| java | pizza | 220 |
| java | pizza | 0 |
위와 같은 경우 Map<Key, Value List>값은 {java, pizza, (0, 200, 220)} 처럼 집어넣어져있을 것이다.
그러므로, 150점 이상인 사람을 구하기 위해 search를 해야한다.
binarySearch를 해야하는데 X(특정점수)점 이상인 경우를 구하기 위해서는 X를 기준으로 BinarySearch하여
index값을 찾으면 구할수있다.
List.size() - index = X점 이상인 사람 수
예시로 설명하면 0, 200, 220 중에서 150 이상인 지점은 200이므로 index=1이다.
따라서 List.size(=3) - index(=1) = 2명 이 최종적인 count 값이다.
코드
import java.util.*;
import java.util.Map.Entry;
class Solution {
String[][] items = {{"cpp", "java", "python"}, {"frontend", "backend"}, {"junior", "senior"}, {"pizza", "chicken"}};
public Integer[] solution(String[] info, String[] query) {
List<Integer> answer = new ArrayList<>();
Map<String, List<Double>> map = new HashMap<>();
for (String str : info) {
String[] s = str.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 4; i++) {
sb.append(s[i]);
}
double v = Integer.parseInt(s[4]);
map.putIfAbsent(sb.toString(), new ArrayList<>());//ArrayList일단 틀 만들어놓기
map.get(sb.toString()).add(v);//value에 코테점수를 Arraylist .add
}
for (Entry<String, List<Double>> e : map.entrySet()) {//key에 대하여
Collections.sort(e.getValue());//value값(코테점수)을 정렬.
}
for (String q : query) {
q = q.replaceAll(" and", "");
String[] s = q.split(" ");//점수랑 자름.
int v = Integer.parseInt(s[4]);//v=점수
Set<String> result = new TreeSet<>();//아래 dfs에서 추가
parse("", s, 0, result);//dfs에서 result add
int cnt = 0;
for (String str : result) {
List<Double> list = map.get(str);//각 str에 해당하는 list를 불러와
if (list == null) continue;//해당하는 값에 점수가 없으면 pass
cnt += upperbound(list, v);//개수 증가
}
answer.add(cnt);//정답에 추가
}
return answer.toArray(new Integer[0]);
}
private void parse(String current, String[] query, int depth, Set<String> result) {
if (depth == query.length - 1) {//쿼리 길이까지 dfs로 탐색하다가 최종추가.
result.add(current);
return;
}
if (query[depth].equals("-")) {//"상관없음"인경우
for (String s : items[depth]) { //재귀로 현재까지 더해진string에 items에서 해당하는 항목경우 각각 재귀. for문.
parse(current + s, query, depth + 1, result);
}
} else {//"특정 언어"와 같은 경우는 current값에 쿼리 나머지값 더해줌
parse(current + query[depth], query, depth + 1, result);
}
}
private int upperbound(List<Double> list, int num) {
int s = 0;
// int e = list.size();
// while (s < e) {
// int mid = (s + e) / 2;
// if (list.get(mid) >= num) {//찾은값>목표값 or 값찾으면!
// e = mid;//왼쪽으로or 해당값으로.
// } else {//찾은값<목표값
// s = mid + 1;//오른쪽으로.
// }
// }
int index = Collections.binarySearch(list, num-0.5);
index = -(index + 1);
return list.size() - index;//해당점수이상인 사람들이니까
}
}
upperbound 부분을 Collections.binarySearch 메소드를 이용하기위해서 전에 코드의 List를 Double형으로 바꿨다.
(upperbound주석)
Integer로 하는 경우에는 upperbound를 반올림하여 찾는것이 불가능하여 계속해서 코드에 실패했다.
[자바] Collections.binarySearch 함수
java.util.Collections.binarySearch() 함수는 정렬된 리스트에서 오브젝트의 위치를 반환하는 java.util.Collections 클래스 메소드입니다. 반드시 정렬 된 상태여야 합니다. 이진 탐색으로 값을 찾기 때문에 정
tadomstudio.tistory.com
binarySearch의 경우 위 블로그에서 언급한것과 같이
search 대상을 찾았을 때는 그 대상의 위치를,
만약 찾지 못했을때는 (- insertion point) - 1에 해당하는 값을 리턴하게 됩니다.
따라서, index값을 위처럼 = -(index +1)로 값변환 해주는 것이다.
아래는 Integer List로 binarySearch를 수작업으로 구현하는 경우의 코드이다.
import java.util.*;
import java.util.Map.Entry;
class Solution {
String[][] items = {{"cpp", "java", "python"}, {"frontend", "backend"}, {"junior", "senior"}, {"pizza", "chicken"}};
public Integer[] solution(String[] info, String[] query) {
List<Integer> answer = new ArrayList<>();
Map<String, List<Integer>> map = new HashMap<>();
for (String str : info) {
String[] s = str.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 4; i++) {
sb.append(s[i]);
}
int v = Integer.parseInt(s[4]);
map.putIfAbsent(sb.toString(), new ArrayList<>());//ArrayList일단 틀 만들어놓기
map.get(sb.toString()).add(v);//value에 코테점수를 Arraylist .add
}
for (Entry<String, List<Integer>> e : map.entrySet()) {//key에 대하여
Collections.sort(e.getValue());//value값(코테점수)을 정렬.
}
for (String q : query) {
q = q.replaceAll(" and", "");
String[] s = q.split(" ");//점수랑 자름.
int v = Integer.parseInt(s[4]);//v=점수
Set<String> result = new TreeSet<>();//아래 dfs에서 추가
parse("", s, 0, result);//dfs에서 result add
int cnt = 0;
for (String str : result) {
List<Integer> list = map.get(str);//각 str에 해당하는 list를 불러와
if (list == null) continue;//해당하는 값에 점수가 없으면 pass
cnt += upperbound(list, v);//개수 증가
}
answer.add(cnt);//정답에 추가
}
return answer.toArray(new Integer[0]);
}
private void parse(String current, String[] query, int depth, Set<String> result) {
if (depth == query.length - 1) {//쿼리 길이까지 dfs로 탐색하다가 최종추가.
result.add(current);
return;
}
if (query[depth].equals("-")) {//"상관없음"인경우
for (String s : items[depth]) { //재귀로 현재까지 더해진string에 items에서 해당하는 항목경우 각각 재귀. for문.
parse(current + s, query, depth + 1, result);
}
} else {//"특정 언어"와 같은 경우는 current값에 쿼리 나머지값 더해줌
parse(current + query[depth], query, depth + 1, result);
}
}
private int upperbound(List<Integer> list, int num) {
int s = 0;
int e = list.size();
while (s < e) {
int mid = (s + e) / 2;
if (list.get(mid) >= num) {//찾은값>목표값 or 값찾으면!
e = mid;//왼쪽으로or 해당값으로.
} else {//찾은값<목표값
s = mid + 1;//오른쪽으로.
}
}
return list.size() - e;//해당점수이상인 사람들이니까
}
}
'코딩테스트 > Java' 카테고리의 다른 글
| (2021카카오) 신규 아이디 추천 Java (0) | 2021.02.22 |
|---|---|
| (2020카카오) 수식최대화 Java (0) | 2021.02.17 |
| (2021카카오) 메뉴 리뉴얼 Java (2) | 2021.02.09 |
| (2020카카오) 기둥과 보 설치 Java (0) | 2021.02.03 |
| (2018카카오) 자물쇠와 열쇠 Java (0) | 2021.01.28 |