글이 복잡하게 쓰여있지만 이해하기 그리 어렵지 않다. result에 실패율이 높은 순으로 정렬해서 return 해주면 되는데 어떻게 실패율을 구할 것인가가 중요하다 우선 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 인데 현재 스테이지 개수 / 현재보다 크거나 같은 스테이지의 개수로 치환 가능하다. 따라서 전처리를 통해 stages의 원소들이 몇 번 등장했는지와 가장 큰 값을 구해놓는다. 가장 큰 값은 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다. 조건 때문에 필요한데 for 문을 돌리면서 i 값이 가장 큰 값보다 크다면 실패율을 0으로 push 해줘야 하기 때문이다. pair벡터를 로 선언해주는데 idx와 fail rate를 ..

begin에서 target이 될 때까지 DFS탐색을 하면서 총 몇 번에 변환이 완료되는지 구하면 된다. 단어는 오직 한 글자씩만 변할 수 있으니 반복문을 통해서 각각 단어들을 비교해주고 차이가 1이라면 DFS를 재귀 호출해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include using namespace std; bool vis[51]; int ans = 100000; void DFS(string cur, string target, vector ar, int cnt, int n, int sum) { if (cur == target) { an..

문자 배열이 주어지면 각 자릿수로 만들 수 있는 모든 경우의 수를 따져서 소수가 되는 수가 몇 개인지 따져보는 문제다. 소수는 에라토스테네스의 체로 쉽게 구할 수 있지만 문제는 '어떻게 모든 경우의 수를 따지는가'이다. 우리는 두 가지 경우로 풀 수 있다. dfs로 풀던가 next_permutation으로 풀던가 둘 중 하나로 풀면 된다. 나는 next_permutation으로 풀었다. #include #include #include #include using namespace std; vector sieve; void era(int n) { sieve.resize(n + 1, true); sieve[0] = sieve[1] = false; for (int i = 2; i * i

문제 정답의 배열이 주어지면 1번 수포자부터 3번 수포자까지 가장 많은 정답을 받은 사람을 answer 배열에 넣으면 된다. 수포자의 반복되는 패턴을 a, b, c 배열에 담아 answers 인덱스와 함께 돌려가면서 카운트를 올려주면 된다. #include #include #include using namespace std; vector solution(vector answers) { vector answer; vector 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 C(3); int ai = 0, bi = 0, ci = 0; for (auto i : answers) { if (i == a[ai++]) { ..

1차원 배열이 주어지면 그 수에서 두 개를 뽑아서 더해주면 된다. 단 중복을 허용하지 않고 오름차순으로 정렬해야 한다. 제한 사항을 보면 numbers의 길이가 100 이하이다. 따라서 이중 포문으로 해줘도 \(O(N^2)\)의 시간복잡도를 가지기에 중복을 방지하는 stl set을 사용해서 자기 자신인 i == j 인 경우를 제외하고 전부 넣어준다. 이후에 반복문을 모두 돌았다면 answer에 삽입해주면 된다. 1234567891011121314151617181920#include #include #include using namespace std; vector solution(vector numbers) { vector answer; set s; int n = numbers.size(); for (in..

N * N 행렬에 각각 캐릭터의 번호가 주어지면 Stack에 넣어서 같은 번호가 나오면 pop 하고 아니면 push 하는 쉬운 문제였다. #include #include #include using namespace std; int pick(vector& 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 board, vector moves) { int answer = 0; stack s; for (int i = 0; i < moves..