문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.
- 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
- 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
- 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
- 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?
물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.
- 코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
- 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
- backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
- 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
- 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?
즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.
* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
[문제]
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
- info 배열의 크기는 1 이상 50,000 이하입니다.
- info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
- 개발언어는 cpp, java, python 중 하나입니다.
- 직군은 backend, frontend 중 하나입니다.
- 경력은 junior, senior 중 하나입니다.
- 소울푸드는 chicken, pizza 중 하나입니다.
- 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- query 배열의 크기는 1 이상 100,000 이하입니다.
- query의 각 문자열은 "[조건] X" 형식입니다.
- [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
- 언어는 cpp, java, python, - 중 하나입니다.
- 직군은 backend, frontend, - 중 하나입니다.
- 경력은 junior, senior, - 중 하나입니다.
- 소울푸드는 chicken, pizza, - 중 하나입니다.
- '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
- X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.
[입출력 예]
info | query | result |
["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] | ["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"] | [1,1,1,1,2,4] |
입출력 예에 대한 설명
지원자 정보를 표로 나타내면 다음과 같습니다.
언어 | 직군 | 경력 | 소울 푸드 | 점수 |
java | backend | junior | pizza | 150 |
python | frontend | senior | chicken | 210 |
python | frontend | senior | chicken | 150 |
cpp | backend | senior | pizza | 260 |
java | backend | junior | chicken | 80 |
python | backend | senior | chicken | 50 |
- "java and backend and junior and pizza 100" : java로 코딩테스트를 봤으며, backend 직군을 선택했고 junior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 100점 이상 받은 지원자는 1명 입니다.
- "python and frontend and senior and chicken 200" : python으로 코딩테스트를 봤으며, frontend 직군을 선택했고, senior 경력이면서 소울 푸드로 chicken을 선택한 지원자 중 코딩테스트 점수를 200점 이상 받은 지원자는 1명 입니다.
- "cpp and - and senior and pizza 250" : cpp로 코딩테스트를 봤으며, senior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 250점 이상 받은 지원자는 1명 입니다.
- "- and backend and senior and - 150" : backend 직군을 선택했고, senior 경력인 지원자 중 코딩테스트 점수를 150점 이상 받은 지원자는 1명 입니다.
- "- and - and - and chicken 100" : 소울푸드로 chicken을 선택한 지원자 중 코딩테스트 점수를 100점 이상을 받은 지원자는 2명 입니다.
- "- and - and - and - 150" : 코딩테스트 점수를 150점 이상 받은 지원자는 4명 입니다.
풀이 방법 생각
처음엔 그냥 순회해서 풀었다가 효율성이 0점 나오는 것을 보고 다시 생각했다. map에 넣어서 확인해서 풀기 위해 각 info마다 가능한 가짓수가 16가지로 나오게 되는데 모두 map에 key로 넣어주 점수를 value로 넣어주었다. 하다가 보면 각 key값 마다 여러 점수가 있기 때문에 Arraylist를 넣어서 여러 점수를 넣어주었고 몇 명인지 확인할 때는 이진탐색으로 인덱스를 가져와서 계산했다.
내 코드
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
class Solution {
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
HashMap<String, ArrayList<Integer>> map = new HashMap<>();
for (int i = 0; i < info.length; i++) {
allSearch(info[i], map);
}
for (String str : map.keySet()) {
Collections.sort(map.get(str));
}
for (int i = 0; i < query.length; i++) {
String[] s = query[i].split(" ");
String str = s[0] + s[2] + s[4] + s[6];
int search = Integer.parseInt(s[7]);
if (map.containsKey(str)) {
answer[i] = map.get(str).size() - binarySearch(map.get(str), search);
} else answer[i] = 0;
}
return answer;
}
void allSearch(String info, HashMap<String, ArrayList<Integer>> map) {
info = info.replaceAll("\\s", "!-!");
String[] s = info.split("!");
for (int i = 0; i < 2; i++) {
for (int j = 2; j < 4; j++) {
for (int k = 4; k < 6; k++) {
for (int u = 6; u < 8; u++) {
String str = s[i] + s[j] + s[k] + s[u];
int grade = Integer.parseInt(s[8]);
if (map.containsKey(str)) {
map.get(str).add(grade);
} else {
ArrayList<Integer> list = new ArrayList<>();
list.add(grade);
map.put(str, list);
}
}
}
}
}
}
int binarySearch(ArrayList<Integer> list, int search) {
int l = 0;
int r = list.size() - 1;
while (l <= r) {
int mid = (r + l) / 2;
if (list.get(mid) == search){
while (true) {
if (mid != 0 && list.get(mid - 1) == search) {
mid--;
continue;
} else
return mid;
}
}
if (list.get(mid) < search) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l;
}
}
다른 사람 풀이
import java.util.ArrayList;
import java.util.HashMap;
class Solution {
static final HashMap<String,Integer> idx = new HashMap<>(){
{
put("java",0);put("python",1);put("cpp",2);
put("backend",0);put("frontend",1);
put("junior",0);put("senior",1);
put("pizza",0);put("chicken",1);
}
};
static int idxs[][] = {{0,1,2},{0,1},{0,1},{0,1}};
static int[][][][][] map;
public int[] solution(String[] info, String[] query) {
map = new int[3][2][2][2][100001];
for (int i=0;i<info.length;i++){
String str[] = info[i].split(" ");
int a = idx.get(str[0]);
int b = idx.get(str[1]);
int c = idx.get(str[2]);
int d = idx.get(str[3]);
int score = Integer.parseInt(str[4]);
map[a][b][c][d][score]++;
}
for (int i=0;i<=2;i++){
for (int j=0;j<=1;j++){
for (int k=0;k<=1;k++){
for (int l=0;l<=1;l++){
int sum=0;
for (int s=100000;s>=1;s--){
sum+=map[i][j][k][l][s];
map[i][j][k][l][s]=sum;
}
}
}
}
}
int ans[] = new int[query.length];
for (int i=0;i<query.length;i++){
String str[] = query[i].split(" and ");
ArrayList<String> arr = new ArrayList<>();
String sps[] = str[3].split(" ");
arr.add(str[0]);arr.add(str[1]);arr.add(str[2]);arr.add(sps[0]);arr.add(sps[1]);
ans[i] = find(arr,new int[4],0);
}
return ans;
}
static int find(ArrayList<String> str,int nums[],int index){
if (index==4){
return map[nums[0]][nums[1]][nums[2]][nums[3]][Integer.parseInt(str.get(4))];
}
int sum=0;
if (str.get(index).equals("-")){
for (int i=0;i<idxs[index].length;i++){
nums[index]=i;
sum += find(str,nums,index+1);
}
}else{
nums[index] = idx.get(str.get(index));
sum += find(str,nums,index+1);
}
return sum;
}
}
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
튜플 (0) | 2021.09.13 |
---|---|
신규 아이디 추천 (0) | 2021.09.09 |
자물쇠와 열쇠 (0) | 2021.09.08 |
문자열 압축 (0) | 2021.09.07 |
괄호 변환 (0) | 2021.09.07 |