2019 카카오 개발자 겨울 인턴십 코딩테스트 혼내주기

 

 

 

다음주 토요일에 있는 2021 카카오 인턴 코딩테스트를 준비하기 위해 2019 카카오 겨울 인턴십 기출문제를 풀어봤다. 2020 카카오 인턴 코테와 마찬가지로 4솔. 

풀이

1번 크레인 인형뽑기 게임
엄청 쉬운 문젠데 스택에 넣는 for문에 범위 설정을 잘못해서 1시간 넘게 붙잡고 있었다...
세로칸 하나마다 스택을 만들어서 풀었다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    int n = board.size();
    
    stack<int> rows[n];
    for(int j = 0; j < n; ++j) {
        for(int i = n-1; i >= 0; --i) {
            if(board[i][j] == 0) break;
            rows[j].push(board[i][j]);
        }
    }
    
    stack<int> stk;
    
    for(int move : moves) {
        if(rows[move-1].empty()) continue;
         
        // 터지는 경우
        if(!stk.empty() && stk.top() == rows[move-1].top()) {
            stk.pop();
            answer += 2;
        }
        // 안터지는 경우
        else stk.push(rows[move-1].top()); 

        rows[move-1].pop();
    }
    
    return answer;
}

 

 

2번 튜플
문자열 처리만 잘 하면 쉽다. 집합의 크기가 증가하는 순서대로 정렬해서 새로운 숫자를 넣으면 된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool check[100000];

bool cmp(const vector<int>& a, const vector<int>& b) {
    return a.size() < b.size();
}

vector<int> solution(string s) {
    vector<int> answer;
   
    vector<int> arr[500];
    int sze = s.size()-1;
    
    // parse
    string num = "";
    int idx = 0;
    bool flag = false;
    for(int i = 1; i < sze; ++i) {
        if(s[i] == '{') {
            flag = true;
        }
        else if(flag && s[i] == ',') {
            arr[idx].push_back(stoi(num));
            num = "";
        }
        else if(flag && s[i] == '}') {
            arr[idx++].push_back(stoi(num));
            num = "";
            flag = false;
        }
        else if(s[i] == ',') {}
        else {
            num += s[i];
        }
    }

    sort(arr, arr+idx, cmp);

    for(int i = 0; i < idx; ++i) {
        for(int a : arr[i]){
            if(check[a]) continue;
            check[a] = true;
            answer.push_back(a);
        }
    }
    
    return answer;
}

 

 

3번 불량 사용자
경우의 수가 최대 8!이기 때문에 완전탐색으로 매칭해준다. 순서가 다르지만 같은 조합인 경우를 처리하기 위해 비트마스크를 사용했는데, 잘 떠올린 것 같아서 뿌듯하다. 한번 꼬였으면 시간 무진장 잡아먹었을 것 같다.

#include <string>
#include <vector>
#include <unordered_map>
#include <cstring>

using namespace std;

int cache[1<<8];
int users, banned;

bool match(string a, string b) {
    if(a.size() != b.size()) return false;
    for(int i = 0; i < a.size(); ++i) {
        if(a[i] != b[i] && b[i] != '*') return false;
    }
    return true;
}

int d(const vector<string>& user_id, const vector<string>& banned_id, int idx, int visited) {
    int& ret = cache[visited];
    if(ret != -1) return 0;
    
    if(idx == banned) {
        return ret = 1;
    }
    
    ret = 0;
    for(int i = 0; i < users; ++i) {
        if(visited & (1 << i)) continue;
        if(match(user_id[i], banned_id[idx])) {
            ret += d(user_id, banned_id, idx+1, visited | (1<<i));
        }
    }
    
    return ret;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    users = user_id.size();
    banned = banned_id.size();
    
    memset(cache, -1, sizeof(cache));
    answer = d(user_id, banned_id, 0, 0);
    
    return answer;
}

 

 

4번 호텔 방 배정
풀릴 듯 안 풀릴 듯 하다가 못풀고 나중에 다른 사람의 풀이를 찾아봤다. 유니온 파인드로 부모를 다음 순서의 숫자로 정해놓으면 된다.
아직 유니온 파인드 문제들을 유니온 파인드로 접근해야 한다는 것을 파악하기가 힘들다. k범위를 어떻게 처리할 지 고민하다가 꼬여버린 것 같기도 하고...
그래도 풀고 보니 좋은 문제다. '유니온 파인드를 이렇게도 활용할 수 있구나'와 해쉬를 이용한 좌표 압축?을 배운 기분.

#include <bits/stdc++.h>
using namespace std;

const long long MAX = 1000000000000;
unordered_map<long long, long long> um;

long long getParent(long long u) {

    if(um.find(u) == um.end()) return u;
    return um[u] = getParent(um[u]);
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;

    for(long long room : room_number) {
        long long newRoom = getParent(room);
        answer.push_back(newRoom);
        um[newRoom] = newRoom + 1;
        
    }
    return answer;
}

 

 

 

5번 징검다리 건너기
처음에 simulate 함수를 전부다 건너보는 방식으로 구현했다가 시간 초과때문에 조금 헤맸다. 그냥 O(n)으로 구할 수 있다.
나는 이분 탐색으로 풀었는데, 다른 사람의 풀이를 보니 슬라이딩 윈도우로 O(n)으로 풀리기도 하는 모양이다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool simulate(vector<int> stones, int friends, int jump) {
    int n = stones.size();
    
    int idx = -1;
    while(1) {
        for(int i = 1; i <= jump; ++i) {
            if(idx + i >= n) return true;
            else if(stones[idx+i] >= friends) {
                idx += i;
                break;
            }
            if(i == jump) return false;
        }
    }
    return false;
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    
    int s = 0, e = 2e8+1;
    while(s < e) {
        // 친구 숫자
        int mid = (s+e) / 2;
        
        bool able = simulate(stones, mid, k);
        if(able) s = mid+1;
        else e = mid;
    }
    
    return s-1;
}

 

지금까지 두개의 기출을 풀어봤는데 둘 다 4솔이었다. 다음주 실전에서도 이렇게 4솔은 하고 싶다.
또 프로그래머스 기준 4단계로 나오는 문제는 계속 못풀었는데, 재능의 부족인건지 노력의 부족인건지 여기까지인가 싶어서 아쉽다.