2019 카카오 개발자 겨울 인턴십 문제 ①

 

 

2019 카카오 개발자 겨울 인턴십

 

 

#1 크레인 인형뽑기 게임

스택 문제. 벡터로 구현했다.

#include <string>
#include <vector>
using namespace std;
 
int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> v;	// as Stack
    int N = board.size();
 
    for (int m : moves) {
    	// Find position
        int idx = 0;
        while (idx < N && !board[idx][m-1]) idx++;
        
        // Pick Up & Get Answer
        if (idx < N) {
            int tar = board[idx][m-1];
            board[idx][m-1] = 0;
            if (!v.empty() && tar == v.back()) v.pop_back(), answer+=2;
            else v.push_back(tar);
        }
    }
    return answer;
}

 

 

#2 튜플

부분 문자열을 먼저 벡터에 넣고 크기 순으로 정렬한 뒤 원소를 차례대로 찾았다.

너무 복잡하게 푼 것 같다,, 인덱스도 헷갈리고 시간도 꽤 오래 걸리는 것 같은데 이 방법 뿐이 없는건지

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool in[1000001];
vector<int> tup[501];
bool sorttup(vector<int> A, vector<int> B) { return A.size() < B.size(); };
vector<int> solution(string s) {
    vector<int> answer;
 
    // {{1,21,3},{21,1},{1,21,445,3},{21}}
    // 1 , w(++) 2 1 , w(++) 3 } f(+=2)
    // 2 1 , w(++) 1 } f(+=2) 1
    // consider i++
    
    // Get Substr
    int N = 0, elem;
    for (int i = 2; i < s.size(); ++N, i += 2) {
        while (s[i] != '}') {
            elem = (int)(s[i++]-'0');
            while (s[i] != ',' && s[i] != '}') {
                elem *= 10, elem += (int)(s[i++] - '0');
            }
            tup[N].push_back(elem);
            if (s[i++] == '}') break;
        }
    }
    
    // Sort
    sort(tup, tup + N, sorttup);    
    
    // Get ANS
    answer.push_back(tup[0][0]); in[tup[0][0]] = true;
    for (int i = 1; i < N; ++i) {
        for (int e : tup[i]) {
            if (!in[e]) { answer.push_back(e); in[e] = true; break; }
        }
    }
    return answer;
}

 

 

#3 불량 사용자

1. banned_id마다 짝지을 수 있는 user_id의 인덱스를 idx 배열에 추가한다.

2. 이제 ban은 상관이 없다. idx배열을 사이즈 따라 정렬한다.

3. idx벡터 크기가 1이면 반드시 한 개의 user을 선택할 수 있단 소리다. 그에 맞게 initstate를 만들어준다.

4. 여러 개 선택할 수 있는 경우에 대해 Count한다.

이때 순열이 아닌 조합 수를 세야 하므로 일반적인 recursion으로는 안 됨.

따라서 bitmasking이용, bool배열로 해당 조합이 선택됐는지 체크한다.

N≤8이라서 이렇게 풀었는데 이래도 되는 건가???? 너무 돌아가는 게 아닌가 싶다 ㅠㅠ 왜 모든 문제가 그런 느낌인지

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool selected[257];
vector<int> idx[8];
bool sortidx(vector<int> A, vector<int> B) {
    return A.size() < B.size();
}
void Count(int b, int state, int FIN, int* ans) {
    if (b == FIN) {
        if (!selected[state]) selected[state]=true, (*ans)++;
        return;
    }
 
    for (int u : idx[b]) {
        if (!(state & (1 << u))) Count(b + 1, state | (1 << u), FIN, ans);
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    int B = banned_id.size();
 
    // Find possible pair of ban-user
    int b = 0;
    for (string ban:banned_id) {
        int u = 0;
        for (string user:user_id) {
            if (ban.size() != user.size()) { ++u; continue; }
 
            int i = 0;
            for (; i < ban.size(); ++i) {
                if (ban[i] == '*') continue;
                else if (ban[i] != user[i]) break;
            }
            if (i == ban.size()) idx[b].push_back(u);
            ++u;
        }
        ++b;
    }
 
    // Sort for effective recursion
    sort(idx, idx + B, sortidx);
    
    // Count ANS use bitmasking
    int initstate = 0;
    for (b = 0; b < B; ++b) {
        if (idx[b].size() == 1) initstate |= (1 << idx[b][0]);
        else break;
    }
    Count(b, initstate, B, &answer);
 
    return answer;
}

 

 

 

 

프로그래머스 문제는 처음 풀어보는데 여러모로 익숙치 않다