[알고리즘, SQL] 2022 Dev-Matching: 웹 백엔드 개발자(하반기) 코딩테스트 후기

2022 Dev-Matching: 웹 백엔드 개발자 코딩테스트 후기입니다
2시간 동안 진행됐고, 알고리즘 3문제, SQL 1문제가 출제되었습니다.
알고리즘 난이도는 쉬운 편이며, 3문제를 푸는데 55분 걸렸고, SQL이 기억이 안나서 30분정도 걸렸습니다..ㅋㅋㅋ
모든 문제 푸는데 시간이 얼마 안 걸려서 변별력이 있는지는 모르겠네요.
문제 이름이 기억이 안나서 대강 비슷한 이름으로 작성하였습니다.

A. 아이디 추천 (소요시간 : 13분)

알고리즘 : 정렬, 단순구현
리스트 내에 사용자가 가입하려는 id가 있는지 확인하고, 있을 경우 새로운 아이디를 추천해주는 단순 정렬, 구현 문제입니다.
커스텀 정렬을 사용해서 문자열이 바뀌어도 다시 처음부터 조회하지 않도록 하여야 합니다
(기존 정렬은 cow10이 cow9보다 앞입니다.)

 

< CODE >

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;

bool cmp(const string& a, const string& b) {
    if (a.length() == b.length())
        return a < b;
    else
        return a.length() < b.length();
}

string solution(vector<string> registered_list, string new_id) {
    string answer = new_id;
    string S = "";
    int N = 0;

    for (int i = 0; i < answer.length(); i++) {
        if (answer[i] >= '0' && answer[i] <= '9') {
            N *= 10;
            N += answer[i] - '0';
        }
        else
            S += answer[i];
    }

    sort(registered_list.begin(), registered_list.end(),cmp);

    for (int i = 0; i < registered_list.size(); i++) {
        if (registered_list[i].compare(answer) == 0) {
            N++;
            answer = S + to_string(N);
        }
    }

    return answer;
}

 

B. 전쟁 (소요시간 : 26분)

알고리즘 : DFS, 정렬
플러드필 문제입니다. 윗 문제처럼 커스텀 정렬 함수를 만들어서 영역이 큰 순서, 그리고 알파벳이 느린 순서로 정렬하고 처리하면 쉽게 처리할 수 있습니다.

< CODE >

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;

#define MAX 1005

bool visited[MAX][MAX];
int result[28];
pair<int,int> ret[28];

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };

int mY, mX;

bool cmp(pair<int,int> a, pair<int,int> b) {
    if (a.first == b.first)
        return a.second > b.second;
    return a.first > b.first;
}

bool Safe(int y, int x) {
    if (y >= 0 && x >= 0 && y < mY && x < mX)
        return true;
    return false;
}

void dfs(int y, int x, const vector<string> & maps) {
    visited[y][x] = true;

    ret[maps[y][x] - 'A'].first++;

    for (int i = 0; i < 4; i++) {
        int dY = y + dy[i];
        int dX = x + dx[i];

        if (Safe(dY,dX) && !visited[dY][dX] && maps[dY][dX] != '.') {
            dfs(dY, dX, maps);
        }
    }
}

int solution(vector<string> maps) {
    int answer = 0;
    mY = maps.size();
    mX = maps[0].length();

    for (int i = 0; i < maps.size(); i++) {
        for (int j = 0; j < maps[i].length(); j++) {
            if (!visited[i][j] && maps[i][j] != '.') {
                for (int k = 0; k < 28; k++) {
                    ret[k].first = 0;
                    ret[k].second = k;
                }
                dfs(i, j, maps);

                sort(ret, ret + 28, cmp);

                result[ret[0].second] += ret[0].first;

                for (int k = 1; k < 'Z' - 'A' + 1; k++) {
                    if (ret[k].first != ret[0].first)
                        result[ret[0].second] += ret[k].first;
                    else
                        result[ret[k].second] += ret[k].first;
                }
            }
        }
    }

    for (int i = 0; i < 'Z' - 'A' + 1; i++) {
        answer = max(answer, result[i]);
    }

    return answer;
}

C. 성냥개비로 숫자 만들기 (소요시간 : 16분)

알고리즘 : DP
성냥개비가 최대 50개기 때문에 1차원 단순 DP로 해결하였습니다
점화식 dp[i] = i개를 사용하여 만들 수 있는 숫자의 개수

< CODE >

#include <string>
#include <vector>

using namespace std;

typedef long long int ll;

int need[10] = { 6,2,5,5,4,5,6,3,7,6 };
ll dp[101];

ll solution(int k) {
    long long answer = 0;

    dp[0] = 1;

    if (k == 6)
        dp[6] = 1;

    for (int i = 1; i < 10; i++) {
        dp[need[i]] += 1;
    }

    for (int i = 2; i < k; i++) {
        for (int j = 0; j < 10; j++) {
            dp[i + need[j]] += dp[i];
        }
    }

    return dp[k];
}

D. 호텔 투숙 가능일 조회 (소요시간 : 33분)

SQL : 서브쿼리, group by
SQL은 별로 할 말이 없네요.. SQL 까먹었는데 검색이 가능했어서 검색해가면서 풀었습니다.

< CODE >

select id, name,
IFNULL((select count(*) from schedules 
where id = place_id
group by place_id),0) as '임대 가능일'
from places
where IFNULL((select count(*) from schedules 
where id = place_id
group by place_id),0) != 0
order by id;

 

통과했습니다.

#2022 데브매칭 코딩테스트 #2022 데브매칭 백엔드 코테 #2022 dev 매칭 백엔드 코딩테스트 하반기 #2022 하반기 데브매칭