Junnnho

programmers 길 찾기 게임 : programmers.co.kr/learn/courses/30/lessons/42892

2019 kakao blind recruitment Level3 문제인 길 찾기 게임입니다.

트리를 만들 수 있도록 모든 정점을 노드로 변환해 준 후에 

1개씩 순회하면서 알맞은 위치에 넣어주시면 됩니다.

정확한 설명은 주석을 통하여 작성하였습니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct node{
    int x,y,idx;
    node* left;
    node* right;
};

node* insertNode(node* parent, node* now){ // 일반적인 바이너리 트리의 삽입 형태 입니다.
    if(parent == NULL) return now;
    if(parent->x > now->x) parent->left = insertNode(parent->left, now);
    else parent->right = insertNode(parent->right, now);
    return parent;
}

vector<int> pre;
vector<int> post;

void preorder(node* now){ // 전위순회
    if(now == NULL) return;
    
    pre.push_back(now->idx);
    preorder(now->left);
    preorder(now->right);
}

void postorder(node* now){ // 후위순회
    if(now == NULL) return;
    
    postorder(now->left);
    postorder(now->right);
    post.push_back(now->idx);
}

bool cmp(node& A, node& B){ // y를 오름차순, x를 내림차순 정렬해줍니다.
    if(A.y != B.y) return A.y > B.y;
    return A.x < B.x;
}

vector<node> v;

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    
    for(int i = 0; i<nodeinfo.size(); i++){ // 정점을 노드화 해줍니다.
        v.push_back({nodeinfo[i][0], nodeinfo[i][1], i+1});
    }
    
    sort(v.begin(), v.end(), cmp);
    
    node* root = &v[0]; // y가 가장 큰 값이 루트노드가 됩니다.
    for(int i = 1; i<v.size(); i++){
        root = insertNode(root, &v[i]); // 알맞은 위치를 찾아 삽입합니다.
    }
    
    preorder(root);
    postorder(root);
    answer.push_back(pre);
    answer.push_back(post);
    
    return answer;
}

programmers 오픈채팅방 : programmers.co.kr/learn/courses/30/lessons/42888

level2 의 2019 kakao blind recruitment 에 나온 문제입니다.

문제에서 요구하는대로 순차적으로 모든 문자열들을 검색하면서 uid에 맞는 nickname을 바꿔주면

시간초과가 발생할 것입니다.

이 문제는 record의 마지막까지 전부 다 읽은 후에 현재 유저의 '최종'닉네임만 알면

쉽게 해결할 수 있습니다.

모든 유저의 '최종' 닉네임을 알기 위해서 <키,값> 으로 이루어져 사용되는 map을 이용하여 문제를 해결했습니다.

#include <string>
#include <vector>
#include <map>
using namespace std;

vector<string> solution(vector<string> record) {
    vector<string> answer;
    map<string, string> m;
    
    for(auto i : record){
        string str = i;
        string enter = "";
        string uid = "";
        string nickname = "";
        
        int idx = 0;
        while(str[idx] != ' ') enter += str[idx++];
        idx++;
        while(idx < str.size() && str[idx] != ' ') uid += str[idx++];
        idx++;
        if(enter.compare("Enter") == 0 || enter.compare("Change") == 0){
            while(idx < str.size() && str[idx] != ' ') nickname += str[idx++];
            m[uid] = nickname;
        }
    }
    
    for(auto i : record){
        string str = i;
        string enter = "";
        string uid = "";
        
        int idx = 0;
        while(str[idx] != ' ') enter += str[idx++];
        idx++;
        while(idx < str.size() && str[idx] != ' ') uid += str[idx++];
        
        if(enter.compare("Change") == 0) continue;
        
        if(enter.compare("Enter") == 0){
            answer.push_back(m[uid]+"님이 들어왔습니다.");
        }
        else{
            answer.push_back(m[uid]+"님이 나갔습니다.");
        }
    }
    
    return answer;
}

programmers 실패율 : programmers.co.kr/learn/courses/30/lessons/42889

kakao 2019 blind recruitment 에 나온 첫번째 문제입니다.

level1에 해당하는 쉬운 난이도의 문제이지만 또 그렇다고 너무 대충대충 풀면 틀리기 쉬운 문제이니

항상 문제를 꼼꼼히 읽고 문제에서 요구하는 조건대로 해결하는 연습을 해야할 것 같습니다.

매 스테이지마다 현재 계산해야할 (스테이지에 남은 사람의 수 / 현재 스테이지까지의 전체 사람의 수) 로 나누어주시면 됩니다.

실패'율'을 따지는 문제이기 때문에 소수점 계산을 위해 자료형을 정확히 사용하셔야 합니다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int stage[501];

bool cmp(pair<double,int> &A, pair<double,int> &B){
    if(A.first != B.first) return A.first>B.first;
    return A.second < B.second;
}

vector<int> solution(int N, vector<int> stages) {
    vector<pair<double, int> > answer;
    vector<int> result;
    
    int people = stages.size();
    for(int i = 0; i<stages.size(); i++) stage[stages[i]]++;
    for(int i = 1; i<=N; i++){
        if(stage[i] == 0){
            answer.push_back({0.0, i});
            continue;
        }
        answer.push_back({(double)stage[i]/people, i});
        people -= stage[i];
    }
    
    sort(answer.begin(), answer.end(), cmp);
    
    for(auto i : answer) result.push_back(i.second);
    
    return result;
}

프로그래머스 가사검색 : programmers.co.kr/learn/courses/30/lessons/60060

최근에 백준으로 이분탐색 관련 문제를 조금 풀었었는데 많은 도움이 되었습니다.

level4 분류에 있던데 '트라이' 자료구조를 사용했을 때 level4에 해당하는 문제같고

이분탐색으로 해결하면 level3 에 해당하는 문제가 아닌가 생각됩니다.

솔루션을 간단하게 정리하면 아래와 같습니다.

1. 이분탐색을 위해 words를 정렬해줍니다.

2. queries의 각 문자열 마다 words에 대한 '구간'을 구해줍니다.

3. '구간'탐색은 queries[i]의 각 문자와 인덱스를 가지고 words의 구간에서 lowerbound, upperbound를 찾습니다.

4. upper-lower는 현재 queries의 가능한 모든 경우의 수가 됩니다.

좀더 자세한 내용은 코드에 주석을 통하여 설명하였습니다.

코드가 140줄 가량으로 길긴하지만 

사실상 이분탐색을 위한 함수를 복붙한 것이라 solution 함수만 보시면 될 것 같습니다.

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

using namespace std;

vector<string> words;
vector<string> reverse_words;
vector<string> queries;

// 배열을 길이 우선, 문자열 순으로 정렬합니다.
bool cmp(string& a, string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    else if (a.size() == b.size()) return a < b;
}

// 길이에 대한 lower
int lower_start(int s, int e, int len) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (words[m].size() >= len) e = m;
        else s = m + 1;
    }
    return e;
}

// 길이에 대한 upper
int upper_start(int s, int e, int len) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (words[m].size() > len) e = m;
        else s = m + 1;
    }
    return e;
}

// words의 lower
int lowerbound(int s, int e, char ch, int idx) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (words[m][idx] >= ch) e = m;
        else s = m + 1;
    }
    return e;
}

// words의 upper
int upperbound(int s, int e, char ch, int idx) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (words[m][idx] > ch) e = m;
        else s = m + 1;
    }
    return e;
}

// reverse_words의 lower
int reverselowerbound(int s, int e, char ch, int idx) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (reverse_words[m][idx] >= ch) e = m;
        else s = m + 1;
    }
    return e;
}

// reverse_words의 upper
int reverseupperbound(int s, int e, char ch, int idx) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (reverse_words[m][idx] > ch) e = m;
        else s = m + 1;
    }
    return e;
}

vector<int> solution(vector<string> w, vector<string> q) {
    vector<int> answer;
    
    // 함수사용을 위해 전역으로 초기화하였습니다.
    words = w;
    queries = q;
    
    // 접미사부터 탐색해야하는 문자열을 위해
    // words 배열을 역으로 정렬하였습니다.
    reverse_words = words;
    for (int i = 0; i < reverse_words.size(); i++) 
        reverse(reverse_words[i].begin(), reverse_words[i].end());

    // cmp() 기준으로 정렬해줍니다.
    sort(words.begin(), words.end(), cmp);
    sort(reverse_words.begin(), reverse_words.end(), cmp);

    for (int i = 0; i < queries.size(); i++) {
        string str = queries[i];

        // 접두사인 경우
        if (str[0] != '?') {
            // 동일한 길이에 대한 비교를 위한 구간을 탐색합니다.
            int lower = lower_start(0, words.size(), str.size());
            int upper = upper_start(0, words.size(), str.size());

            // 접두사부터 words에 대입해보면서 이분탐색을 실행합니다.
            for (int i = 0; i < str.size(); i++) {
                if (str[i] == '?') break;

                // 현재 lower, upper는 탐색의 기준이 되기때문에 따로 사용합니다. 
                int l = lower;
                int u = upper;
                
                // 현재 문자str[i]의 lower, upper을 찾음
                lower = lowerbound(l, u, str[i], i);
                upper = upperbound(l, u, str[i], i);
            }
            // 구간끝-구간시작 이 가능한 모든 경우입니다.
            answer.push_back(upper - lower);
        }
        // 접미사인 경우(접두사와 같지만 words를 reverse_words로 사용!)
        else if (str[0] == '?') {
            int lower = lower_start(0, reverse_words.size(), str.size());
            int upper = upper_start(0, reverse_words.size(), str.size());
            reverse(str.begin(), str.end());
            for (int i = 0; i < str.size(); i++) {
                if (str[i] == '?') break;
                
                int l = lower;
                int u = upper;
                lower = reverselowerbound(l, u, str[i], i);
                upper = reverseupperbound(l, u, str[i], i);
            }

            answer.push_back(upper - lower);
        }
    }

    return answer;
}

** 효율성 실행시간