Kcode

글이 복잡하게 쓰여있지만 이해하기 그리 어렵지 않다.

result에 실패율이 높은 순으로 정렬해서 return 해주면 되는데 어떻게 실패율을 구할 것인가가 중요하다

우선 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 인데

현재 스테이지 개수 / 현재보다 크거나 같은 스테이지의 개수로 치환 가능하다.

따라서 전처리를 통해 stages의 원소들이 몇 번 등장했는지와 가장 큰 값을 구해놓는다.

가장 큰 값은 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다. 조건 때문에 필요한데

for 문을 돌리면서 i 값이 가장 큰 값보다 크다면 실패율을 0으로 push 해줘야 하기 때문이다.

pair벡터를 <int, double>로 선언해주는데 idx와 fail rate를 담는다.

첫 번째 예제를 보면

각각의 번호와 몇 번 등장했는지를 구해보면 이렇게 나오는데

스테이지의 총인원수가 8명이니

<1,1> <2,3> <3,2> <4,1> <5,0> <6,1> 

에서 1번의 실패율은 1의 second / n - sum(누적)이다.

정렬은 comp를 통해 쉽게 구현 가능하다.

앞쪽에 있는 기능이 전부 개발되었다면 앞에서부터 기능이 개발되지 않은 것이 나올 때까지 pop 해주고

그 cnt를 answer에 저장해주면 된다.

우선 progresses와 speeds를 전부 큐에 넣어주고 반복문을 통해 0번 위치의 기능을 수행하는 데에

얼마나 걸리는지 세준다. 이후 현재 날 * speed의 front + q의 front가 100보다 크다면 그 기능도

이미 완료되었기 때문에 pop 해주면 된다.

begin에서 target이 될 때까지 DFS탐색을 하면서 총 몇 번에 변환이 완료되는지 구하면 된다.

단어는 오직 한 글자씩만 변할 수 있으니 반복문을 통해서 각각 단어들을 비교해주고

차이가 1이라면 DFS를 재귀 호출해주면 된다.

간단한 BFS 문제였다.

근데 문제에서 주의해야 할 점이 있다.

전역 변수로 선언할 경우 반드시 solution 내에서 초기화를 시켜줘야 한다.

이것만 주의한다면 나머진 쉽게 풀리는 문제다.

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

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    vector<vector<bool>> vis(101, vector<bool>(101, false));
    queue<pair<int, int>> Q;
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    int tmp = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int area = 1;
            if (!vis[i][j] && picture[i][j] != 0) {
                number_of_area++;
                Q.push({ i,j });
                vis[i][j] = true;
                tmp = picture[i][j];
            }
            while (!Q.empty()) {
                auto cur = Q.front(); Q.pop();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (vis[nx][ny] || picture[nx][ny] != tmp) continue;
                    Q.push({ nx,ny });
                    vis[nx][ny] = true;
                    area++;
                }
            }
            max_size_of_one_area = max(max_size_of_one_area, area);
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

문제를 풀다 보면 BFS나 DFS 같은 경우는 특히 자신만의 정형화된 틀을 사용하는데 이 문제에선 그냥 전역 변수에 박아 넣고 푸는 게 정신건강에 이로운 것 같다.

문자 배열이 주어지면 각 자릿수로 만들 수 있는 모든 경우의 수를 따져서 소수가 되는 수가 몇 개인지 따져보는 문제다.

소수는 에라토스테네스의 체로 쉽게 구할 수 있지만 문제는 '어떻게 모든 경우의 수를 따지는가'이다.

우리는 두 가지 경우로 풀 수 있다.

dfs로 풀던가 next_permutation으로 풀던가 둘 중 하나로 풀면 된다.

나는 next_permutation으로 풀었다.

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

vector<bool> sieve;

void era(int n) {
    sieve.resize(n + 1, true);
    sieve[0] = sieve[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (sieve[i]) {
            for (int j = i * 2; j <= n; j += i) sieve[j] = false;
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    sort(numbers.begin(), numbers.end(), greater<int>());
    era(stoi(numbers));
    sort(numbers.begin(), numbers.end());
    
    set<int> ans;
    vector<int> ar;
    for (auto i : numbers) ar.push_back(i - '0');
    
    do {
        for (int i = 0; i <= ar.size(); i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                tmp = (tmp * 10) + ar[j];
            }
            ans.insert(tmp);
        }
    } while (next_permutation(ar.begin(), ar.end()));
    
    for (auto i : ans) if (sieve[i]) answer++;
    
    return answer;
}

문자열의 길이가 7자리니 9,999,999 즉 10,000,000까지 배열을 생성해두면 편하다

나는 문자열을 받아서 내림차순으로 정렬하고 이후 에라토스테네스의 체에 넣어줬다.

이후 다시 정렬해주는 게 중요하다.

    do {
        for (int i = 0; i <= ar.size(); i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                tmp = (tmp * 10) + ar[j];
            }
            ans.insert(tmp);
        }
    } while (next_permutation(ar.begin(), ar.end()));

next_permutation에서 모든 경우의 수를 따져보려면 벡터가 오름차순으로 정렬되어 있어야 한다.

예를 들어서 7, 1 이 벡터에 들어있다면 나오는 경우의 수는 7, 71 밖에 없지만

1, 7로 정렬되어있다면 0, 1, 7, 17, 71로 5개가 나온다.

또한 set을 통해 입력받으면 중복을 알아서 걸러주지만 vector로 하는 게 시간 복잡도면에서는 더 짧다.

ans.insert 대신 vector에 입력받고 정렬 후 중복 제거해주는 게 더 짧게 나왔다.

참여자와 완주자 배열이 주어지면 완주하지 못한 선수의 이름을 리턴하면 되는 쉬운 문제다.

난 map을 이용해서 해결했는데 다른 사람의 풀이를 보니 두 배열을 정렬하고 이름이 같지 않다면 그 이름을 리턴해주는 식으로 풀었다.

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

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    map<string, int> m;
    
    for (auto i : participant) {
        m[i]++;
    }
    for (auto i : completion) {
        m[i]--;
    }
    for (auto i : participant) {
        if (m[i] == 1) answer = i;
    }
    
    return answer;
}

map에 참여자의 이름을 키값으로 value를 하나씩 올려주고, 완주자의 배열을 돌면서 그 개수만큼 줄여주면

마지막에 map에 남아있는 사람이 완주하지 못한 사람이니 리턴해줬다.

문제 정답의 배열이 주어지면 1번 수포자부터 3번 수포자까지 가장 많은 정답을 받은 사람을 answer 배열에 넣으면 된다.

수포자의 반복되는 패턴을 a, b, c 배열에 담아 answers 인덱스와 함께 돌려가면서 카운트를 올려주면 된다.

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

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<int> a = { 1,2,3,4,5 }, b = { 2,1,2,3,2,4,2,5 }, c = { 3,3,1,1,2,2,4,4,5,5 };
    vector<int> C(3);

    int ai = 0, bi = 0, ci = 0;
    for (auto i : answers) {
        if (i == a[ai++]) {
            C[0]++;
            if (ai == 5) ai = 0;
        }
        if (i == b[bi++]) {
            C[1]++;
            if (bi == 8) bi = 0;
        }
        if (i == c[ci++]) {
            C[2]++;
            if (ci == 10) ci = 0;
        }
    }
    int max_v = *max_element(C.begin(), C.end());

    for (int i = 0; i < 3; i++) {
        if (max_v == C[i]) {
            answer.push_back(i + 1);
        }
    }

    return answer;
}

처음엔 이렇게 적어줬는데 첫 예제 2개는 잘 맞고 그 이후로 제출하니 틀려서 고민해보니

ai, bi, ci 이런 식으로 하는 건 너무 위험한 접근법이었다.

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

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<int> a = { 1,2,3,4,5 }, b = { 2,1,2,3,2,4,2,5 }, c = { 3,3,1,1,2,2,4,4,5,5 };
    vector<int> C(3);
    
    for (int i = 0; i < answers.size(); i++) {
        if (answers[i] == a[i % 5]) C[0]++;
        if (answers[i] == b[i % 8]) C[1]++;
        if (answers[i] == c[i % 10]) C[2]++;
    }
    int max_v = *max_element(C.begin(), C.end());
    
    for (int i = 0; i < 3; i++) {
        if (max_v == C[i]) {
            answer.push_back(i + 1);
        }
    }
    
    return answer;
}

나머지 연산자를 사용하니 바로 맞았다...

나머지 연산자를 잘 기억해둬야겠다.

1차원 배열이 주어지면 그 수에서 두 개를 뽑아서 더해주면 된다. 단 중복을 허용하지 않고 오름차순으로 정렬해야 한다.

제한 사항을 보면 numbers의 길이가 100 이하이다. 따라서 이중 포문으로 해줘도

\(O(N^2)\)의 시간복잡도를 가지기에 중복을 방지하는 stl set을 사용해서 

자기 자신인 i == j 인 경우를 제외하고 전부 넣어준다.

이후에 반복문을 모두 돌았다면 answer에 삽입해주면 된다.

N * N 행렬에 각각 캐릭터의 번호가 주어지면 Stack에 넣어서 같은 번호가 나오면 pop 하고 아니면 push 하는 쉬운 문제였다.

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

using namespace std;

int pick(vector<vector<int>>& board, int col) {
    for (int i = 0; i < board.size(); i++) { 
        if (board[i][col] == 0) continue;
        int ret = board[i][col];
        board[i][col] = 0;
        return ret;
    }
    return 0;
}

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> s;
    
    for (int i = 0; i < moves.size(); i++) {
        int tmp = pick(board, moves[i] - 1);
        if (tmp) {
            if (s.empty()) s.push(tmp);
            else {
                if (s.top() == tmp) {
                    answer += 2;
                    s.pop();
                }
                else s.push(tmp);
            }
        }
    }
    
    return answer;
}

나는 moves 수만큼 pick 함수를 사용해서 넣어줬다. 처음에는 

int pick(vector<vector<int>>& board, int col) {
    for (int i = 0; i < board.size(); i++) { 
        if (board[i][col] == 0) continue;
        int ret = board[i][col];
        board[i][col] = 0;
        return ret;
    }
    return 0;
}

이 pick 함수에서 board[col][i] 로 해야 되는 줄 알았는데 반대여서 틀렸었다;;

board에서 뽑았으면 그 후 0으로 바꿔줘야 다음번에 다시 뽑지 않는다.