2021 KAKAO BLIND RECRUITMENT 1차 코딩테스트 (1, 2번)

1번

C++

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

// 1. 모든 대문자를 소문자로 치환
void level1(string& new_id){
    for(int i = 0; i < new_id.size(); i++)
        if(0x41 <= (int)new_id[i] && (int)new_id[i]  <= 0x5a)    
            new_id[i] = char((int)new_id[i]+0x20); 
}

// 2. 알파벳 소문자, 숫자, -, _, . 제외한 문자 제거
void level2(string& new_id){
    for(int i = new_id.size()-1; i >= 0; i--)
        if(!((0x61 <= (int)new_id[i] && (int)new_id[i] <= 0x7a) || (0x30 <= int(new_id[i]) && int(new_id[i]) <= 0x39) || new_id[i] == '-' || new_id[i] == '_' || new_id[i] == '.'))
            new_id.erase(new_id.begin()+i);
}

// 3. 2번이상 연속된 마침표 하나로 치환
void level3(string& new_id){
    for(int i = new_id.size()-1; i > 0; i--)
        if(new_id[i] == '.')
            if(new_id[i-1] == '.')
                new_id.erase(new_id.begin()+i-1);
}

// 4. 마침표가 처음과 끝에 위치하면 제거
void level4(string& new_id){
    if(new_id[new_id.size()-1] == '.')
        new_id.erase(new_id.begin()+new_id.size()-1);
    if(new_id[0] == '.')
        new_id.erase(new_id.begin()+0);
}

// 5. 빈 문자열이면 문자열 a 대입
void level5(string& new_id){
    if(new_id.size() == 0)
        new_id.push_back('a');
}

// 6. 16자 이상이면 15자 이후로 모두 자르기, 단 마지막 문자가 마침표라면 마침표까지 지우기
void level6(string& new_id){
    if(new_id.size() > 15)
        new_id.erase(15);
    if(new_id[new_id.size()-1] == '.')
        new_id.erase(new_id.begin()+new_id.size()-1);
}

// 7. 2자 이하라면 마지막 문자를 길이가 3이 될 때까지 반복해서 붙인다.
void level7(string& new_id){
    if(new_id.size() <= 2)
        while(new_id.size() != 3)
            new_id.push_back(new_id[new_id.size()-1]);
}

string solution(string new_id) {
    level1(new_id);
    level2(new_id);
    level3(new_id);
    level4(new_id);
    level5(new_id);
    level6(new_id);
    level7(new_id);
    return new_id;
}

기본적인 문자열 처리 문제로 조건에 맞게 구현만 해주면 쉽게 해결할 수 있다. string 클래스 메소드들을 찾아가면서 코딩을 하느라 시간이 꽤 오래 걸렸다.

2번

C++

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#define INF 987654321;
using namespace std;

map<string, int> m, appear;
vector<pair<int, string>> candidate[11];

void recursive(string menu)
    if(appear[menu] == 0){
        appear[menu]++;        
        m[menu]++;
    }
    // 재귀 호출
    if(menu.size() > 2){
        for(int i = 0; i < menu.size(); i++){
            string tmp;
            for(int j = 0; j < menu.size(); j++)
                if(i != j)
                    tmp += menu[j];
            recursive(tmp);
        }
    }
}

void solve(vector<string>& orders){
    for(int i = 0; i < orders.size(); i++){
        appear.clear(); 
        string menu = orders[i];
        sort(menu.begin(), menu.end());
        recursive(menu);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    solve(orders);
    for(auto it = m.begin(); it != m.end(); it++)
        for(int i = 0; i < course.size(); i++)
            if(course[i] == it->second)
                candidate[it->first.size()].push_back(make_pair(it->second, it->first));
    for(int i = 0; i < course.size(); i++){
        int length = course[i];
        int maxLen = -INF;
        sort(candidate[length].begin(), candidate[length].end());
        for(int j = candidate[length].size()-1; j >= 0; j--){
            if(maxLen <= candidate[length][j].first){
                maxLen = candidate[length][j].first;
                answer.push_back(candidate[length][j].second);
            } 
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}

손님들이 주문한 음식 목록으로 코스 요리 메뉴를 선정하는 문제이다. 코스 요리는 음식이 2개 이상이어야 하고, 같은 구성의 요리를 두명 이상의 손님이 주문하여야 한다. 음식의 순서가 달라도 같은 코스 요리이므로 원소가 2개 이상인 조합을 구하면 된다.

조합을 구하는 함수는 각 단계의 문자열로 만들 수 있는 _nC_n-1 개의 조합을 재귀 호출하여 구현했다.

구한 경우의 수 들을 문제에 조건에 맞도록 잘 분류 & 정렬 해주면 끝. 주의할 점은 요리 목록이 항상 사전순으로 정렬되어 주어지지 않는다는 점이다.

입력 범위가 작아 대부분 2초안으로 해결되는 것 같다.

후기

1번 문제를 풀며 문자열 처리 공부를 해야겠단 생각이 들었다. 2번 문제를 풀 땐 마음이 급해 설계와 코드 작성을 동시에 한 것이 문제였다. 문제도 잘못 읽게 되고 결과적으로 디버깅에 많은 시간이 걸렸다.