2021 프로그래머스 월간 코딩 챌린지 시즌2 후기

4월 15일 목요일 프로그래머스에서 주최하는 월간 코딩 챌린지 시즌2를 보았다.

1차, 2차 총 8문제가 나오며 저번 주에 첫 번째 대회를 보았다.

1번은 level1도 못 미치는 수준이고 2번은 level1.5 정도이고 3번은 level 3으로 책정이 되었지만 개인적으로 level 3~4 사이인 듯하다. 4번은 사실 풀 수 없을 거라 생각하고 시도도 안 했고 level 5로 나온 거 보니 상당히 어려운 문제였던 것 같다.

<1번>

programmers.co.kr/learn/courses/30/lessons/76501

코딩테스트 연습 - 음양 더하기

사실 뭐 너무 쉬워서 풀이가 필요할까 싶다..

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> a, vector<bool> s)
{
    int answer = 0;
    for (int i = 0; i < a.size(); i++)
    {
        if (s[i])
            answer += a[i];
        else
            answer += -1 * a[i];
    }
    return answer;
}

7초인가? 10초 정도 걸렸고 7등했다..

1등 하신 분은 실시간으로 뜨는데 3~4초 정도 걸리신 거 같다.

---

<2번>

programmers.co.kr/learn/courses/30/lessons/76502

코딩테스트 연습 - 괄호 회전하기

약 15분인가 걸렸다.

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

using namespace std;

int solution(string s)
{
    int answer = 0;
    int size = s.size();
    for (int i = 0; i < size; i++)
    {
        stack<char> a;
        int flg = 0;
        for (int j = 0; j < size; j++)
        {
            if (s[j] == '{' || s[j] == '[' || s[j] == '(')
            {
                a.push(s[j]);
                flg = 1;
            }
            if (s[j] == '}' && a.top() == '{')
                a.pop();
            if (s[j] == ']' && a.top() == '[')
                a.pop();
            if (s[j] == ')' && a.top() == '(')
                a.pop();
        }
        if (a.empty() && flg == 1)
            answer++;
        char c = s[0];
        for (int i = 0; i < size - 1; i++)
            s[i] = s[i + 1];
        s[size - 1] = c;
    }
    return answer;
}

처음에 괜히 벡터로 하려다가 10분 정도 날리고 스택 쓰고 3분 걸렸다.

---

<3번>

programmers.co.kr/learn/courses/30/lessons/76503

코딩테스트 연습 - 모두 0으로 만들기

처음에 한 20분 정도 삽질을 하다가 문득 방법이 떠올라서 그대로 했더니 시간 초과가 우수수 나왔다.

내가 푼 코드 자체는 N^2의 시간 복잡도를 가지는데 몇가지 경우를 제외하고는 모두 시간초과가 뜨는 것으로 보아 아마도 Nlogn 정도의 시간복잡도를 가지는 풀이가 필요했던 것 같다.

그래서 그러려고 노력은 해봤지만 결국 실패..

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

long long solution(vector<int> a, vector<vector<int>> ed)
{
    long long answer = 0;

    // 예외처리
    long long sum = 0;
    int size = a.size();
    for (int i = 0; i < size; i++)
        sum += a[i];
    if (sum != 0)
        return -1;
    //예외처리 끝

    //2차원 배열 생성
    vector<vector<int>> e(size, vector<int>(size, 0));
    for (int i = 0; i < ed.size(); i++)
    {
        e[ed[i][0]][ed[i][1]] = 1;
        e[ed[i][1]][ed[i][0]] = 1;
    }
    //2차원 배열 끝

    vector<pair<int, int>> c;
    //간선 개수 배열 생성 후 정렬
    for (int i = 0; i < size; i++)
    {
        int temp = 0;
        for (int j = 0; j < size; j++)
        {
            if (e[i][j] == 1)
                temp++;
        }
        c.push_back(make_pair(i, temp));
    }
    sort(c.begin(), c.end());
    //정렬 끝

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (e[c[i].first][j] == 1)
            {
                a[j] += a[c[i].first];
                answer += abs(a[c[i].first]);
                a[c[i].first] = 0;
                c[i].second--;
                c[j].second--;
                e[c[i].first][j] = 0;
                e[j][c[i].first] = 0;
            }
        }
    }
    return answer;
}

처음에는 다익스트라로 풀 수 있을까? 생각하여 풀어 보았는데 내가 가진 지식으로는.. 힘들었다.

그다음 생각한 방법이 간선의 개수가 제일 적은 순부터 끝에서 줄여오는 식으로 생각을 하여 풀었는데 결국 풀지 못하고 끝이 났다. 위 코드는 38.9점이 나온 코드다.

---

<4번>

4번은 못 풀었다. 혹여 푸실 분들을 위한 링크를 첨부한다.

programmers.co.kr/learn/courses/30/lessons/76504

코딩테스트 연습 - RPG와 쿼리

---

결과적으로 238.9/400으로 상위 11%가 나오긴 했는데 만약 이 챌린지가 어떤 회사의 코딩 테스트였다면 3번까지는 100점이 나왔어야 합격이 될 것이라고 생각을 한다.

3번은 사실 별로 어려운 문제도 아니었는데.. 너무 이상하고 깊게 생각한 내 잘못이겠지만..

다시 풀어보고 100점을 맞고 글을 수정해야겠다!

---

참고로 평균 점수는 207점이 나왔다.