2021 KAKAO BLIND RECRUITMENT

카카오 문제해설 

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

 

문제 1. 신규 아이디 추천

https://school.programmers.co.kr/learn/courses/30/lessons/72410

프로그래머스

1번은 1번답게 아주쉬운 구현문제였다.

설마 모든 조건이 만족할때까지 while 문을 돌리는 건가? 했는데 그것도 아니고 그냥 딱 7개 조건을 한번씩만 거치면 되는 문제였다.

java의 String 관련 함수들을 머릿속에 잘 넣어두어야 빨리 풀수 있는 문제였다.

class Solution {
    public String solution(String new_id) {
        String answer = "";
        
        answer = new_id.toLowerCase();
        
        answer = answer.replaceAll("[^a-zA-Z0-9-._]","");
        
        while(answer.contains("..")){
            int index = answer.indexOf("..");
            answer = answer.substring(0, index)+answer.substring(index+1);   
        }
        
        if(answer.length() > 0 && answer.startsWith(".")){
            answer = answer.substring(1);
        }
        if(answer.length() > 0 && answer.endsWith(".")){
            answer = answer.substring(0, answer.length()-1);
        }
        
        if(answer.length()==0){
            answer = "a";
        }
        if(answer.length()>=16){
            answer= answer.substring(0,15);
        }
        if(answer.length() > 0 && answer.endsWith(".")){
            answer = answer.substring(0, answer.length()-1);
        }
        while(answer.length()<=2){
            answer = answer.concat(answer.substring(answer.length()-1));
        }
        
        
        
        return answer;
    }
}

 

---

문제 2. 메뉴 리뉴얼

https://school.programmers.co.kr/learn/courses/30/lessons/72411

프로그래머스

저번에 풀어놨던 문제길래 내 코드를 보니까 모이리 복잡하게 했는지 모르겠다.

결론적으로는 각 메뉴별로 가능한 모든 조합을 만들어서 각 조합의 갯수를 센다.

그리고 문자열의 길이가 같은 조합 중 가장 많이 나타난 조합을 구하는 문제였다.

 

순열과 조합을 구하는 함수는 자주 나와서 얼른 체화시켜야 겠다.

 

import java.util.HashMap;
import java.util.Map;
import java.util.Collections;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
 
class Solution {
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        List<String> testList = new ArrayList<String>();
        for(int r = 0; r<course.length; r++){
            HashMap<String, Integer> map = new HashMap<>();
            for(int i=0; i< orders.length; i++){
                boolean[] visited = new boolean[orders[i].length()];
                combination(orders[i], visited, 0, orders[i].length(), course[r],map);
            }
            if(map.size() > 0){
                int maxValue = Collections.max(map.values());
                for(Map.Entry<String, Integer> m : map.entrySet()) {
                    if(m.getValue()==maxValue && maxValue>=2) {
                        testList.add(m.getKey());
                    }
                }
            }
        }
        Collections.sort(testList);
        System.out.println(testList);
        answer = new String[testList.size()];
        int cnt = 0;
        for(String item : testList){
            answer[cnt++] = item;
        }
        return answer;
    }
    static void combination(String arr, boolean[] visited, int start, int n, int r, HashMap<String, Integer> map)       {
        if(r == 0) {
            String res = print(arr, visited, n);
            char[] tmp = res.toCharArray();
            Arrays.sort(tmp);
            
            res = String.valueOf(tmp);
            map.put(res,map.getOrDefault(res,0)+1 );
            
            return;
        } 
 
        for(int i=start; i<n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1, map);
            visited[i] = false;
        }
    }
    static String print(String arr, boolean[] visited, int n) {
        String result = "";
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                result += arr.charAt(i);
            }
        }
        return result;
    }
}

---

문제 3. 순위검색

https://school.programmers.co.kr/learn/courses/30/lessons/72412

프로그래머스

문제를 얕보고 그냥 풀었더니 효율성테스트가 있었다.. 이래서는 점수가 50점도 안나온다.

효율성은 dp의 메모이제이션을 어떻게 할지와 비슷하게 자료구조를 잘 만들면 된다.

 

지원자 “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

각 지원자를 이렇게 그룹화해서 일일히 info를 parsing 하지 않고

미리 분류해둔 그룹에서 X점 이상 맞은 지원자 수를 세주면 된다.

각 그룹을 점수 오름차순으로 정렬하고, X점을 binary search로 찾아내면 빠르게 검색이 가능하다.

 

 

이문제를 풀면서 연습이 많이 됐다.

HashMap 에서 key를 "java backend junior pizza" 이런식으로 두고, value를 점수 리스트 [40, 50, 150] 으로 두었다.

여기에서 언어/분야/경력/소울푸드 각각 "-" 인 그룹에도 추가로 포함시켜준다.

모든 value들의 arraylist는 오름차순으로 sort 한다.

 

 

탐색에서는 query 에 들어온 String 을 Hashmap의 Key 형식과 맞춰서, "java backend junior -" 으로 정제해서 map에서 존재하는지 우선 찾고,

있다면 점수 리스트 중에 query로 들어온 점수값 이상인 사람 수를 찾기만 하면된다.

이때 이미 오름차순으로 해두었기 때문에 점수값보다 크거나 같은 첫 인덱스만 구하면 arraylist.length - 해당 index 로 쉽게 몇명인지를 구할수 있었다.

 

 

* ArrayList<Integer> arrays = map.getOrDefault(key, new ArrayList<Integer>()); //이런식으로도 사용 가능한것도 배웠다

* String.join(" ", list) 함수 : list에 있던 문자열들을 띄어쓰기 포함해서 하나로 합쳐준다.

import java.util.ArrayList;
import java.util.HashMap;
class Solution {
    public static int len;
    public static HashMap<String, ArrayList<Integer>> map;
    
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        map = new HashMap<String, ArrayList<Integer>>();
 
        len = info.length;
        for(String i:info){
            String[] splited = i.split(" ");
            String[] langs = {splited[0], "-"};
            String[] parts = {splited[1], "-"};
            String[] exps = {splited[2],"-"};
            String[] foods = {splited[3],"-"};
            Integer score = Integer.parseInt(splited[4]);
            for(String lang : langs){
                for(String part : parts){
                    for(String exp : exps){
                        for(String food : foods){
                            String[] keydata = {lang,part,exp,food};
                            String key = String.join(" ", keydata);
                            
                            ArrayList<Integer> arrays = map.getOrDefault(key, new ArrayList<Integer>());
                            arrays.add(score);
                            
                            map.put(key, arrays);
                        }
                    }
                }
            }
        }
        
        for (ArrayList<Integer> scoreList : map.values())
            scoreList.sort(null);
 
        
        for(int k=0; k<query.length; k++){
            answer[k] = count(query[k]);
        }
        return answer;
    }
    static int count(String q){
        int count = 0;
        String[] splited = q.split(" and ");
        String[] tmps = splited[3].split(" ");
        String[] keyarrays = {splited[0], splited[1], splited[2], tmps[0]};
        
        int score = Integer.parseInt(tmps[1]);
        String key = String.join(" ", keyarrays);
        
        if(map.containsKey(key)){
            ArrayList<Integer> scorelist = map.get(key);
            int left = 0;
            int right = scorelist.size();
            int mid=(left+right)/2;
            while(left < right){
                mid = (left+right)/2;
                if(scorelist.get(mid)>=score){ 
                    right = mid;
                }
                else if(scorelist.get(mid)<score){
                    left = mid+1;
                }
            }
            count = scorelist.size()-left;        
        }
        return count;
    }
}

 

 

---

문제 5. 광고삽입

 

https://school.programmers.co.kr/learn/courses/30/lessons/72414

프로그래머스

전체 동영상 길이 만큼의 배열을 만들어서, 부분합과 슬라이딩 윈도우 방식으로 구현하는 문제였다.

효율성이 안좋아도 10초이상의 시간초과만 아니면 테스트는 통과하기 때문에 그냥 풀면되긴 한다. 근데 문제 푸는데 이렇게 시간이 오래걸려서 과연 코테를 붙을수나 있긴 한가 의문이들긴 하지만..

 

처음에 시간복잡도를 너무 길게 만들었더니 시간초과 에러가 났다.

불필요한 sort 부분을 지우고 다시 했더니 이번에는 테스트17 답이 틀림..

알고봤더니 int 형 범위를 초과해서 나는 에러였다. (질문게시판 참고)

long 으로 바꾸고나서 정답!

(자료형 주의 또 주의.. 그래도 항상 까먹는듯 ㅠ)

 

import java.util.Arrays;
import java.util.Comparator;
class Solution {
    public static int[] nested;
    public static int playtime;
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        playtime = convert(play_time);
        nested = new int[playtime+1];
        int in, out;
        for(int i=0; i<logs.length; i++){
            String[] sp = logs[i].split("-");
            in = convert(sp[0]); out = convert(sp[1]);
            for(int j=in; j<out; j++){
                nested[j]++;
            }
        }
        int advtime = convert(adv_time);
        long max = Long.MIN_VALUE;
        long [] sum = new long[playtime+2];
        
        int m=0; sum[0]=nested[0];
        for(int i=1; i<=playtime; i++){ //O(N)
            sum[i] = sum[i-1]+nested[i];
        }
        
        int result = 0;
        for(int i=0; i<=playtime-advtime; i++){ //O(N)
            long cnt;
            if(i==0) cnt = sum[i+advtime-1];
            else cnt = sum[i+advtime-1] - sum[i-1];
            
            if(cnt > max){
                max = cnt;
                result = i;
            }
        }
        answer = origin(result);
        
        return answer;
    }
    public String origin(int t){
        String hour = Integer.toString(t/3600); t = t%3600;
        String min = Integer.toString(t/60); t = t%60;
        String sec = Integer.toString(t);
        if(hour.length()<2){ hour = "0".concat(hour);}
        if(min.length()<2){ min = "0".concat(min);}
        if(sec.length()<2){ sec = "0".concat(sec);}
        return hour+":"+min+":"+sec;
    }
    public int convert(String t){
        int result = 0;
        result += (Integer.parseInt(t.substring(0,1))*10 + Integer.parseInt(t.substring(1,2))) * 3600;
        result += (Integer.parseInt(t.substring(3,4))*10 + Integer.parseInt(t.substring(4,5))) * 60;
        result += (Integer.parseInt(t.substring(6,7))*10 + Integer.parseInt(t.substring(7)));
        
        return result;
    }
}