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

앞쪽에 있는 기능이 전부 개발되었다면 앞에서부터 기능이 개발되지 않은 것이 나올 때까지 pop 해주고 그 cnt를 answer에 저장해주면 된다. 우선 progresses와 speeds를 전부 큐에 넣어주고 반복문을 통해 0번 위치의 기능을 수행하는 데에 얼마나 걸리는지 세준다. 이후 현재 날 * speed의 front + q의 front가 100보다 크다면 그 기능도 이미 완료되었기 때문에 pop 해주면 된다. 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 #include #include #include using namespace std; vector solution(vector progresses, vect..

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..

간단한 BFS 문제였다. 근데 문제에서 주의해야 할 점이 있다. 전역 변수로 선언할 경우 반드시 solution 내에서 초기화를 시켜줘야 한다. 이것만 주의한다면 나머진 쉽게 풀리는 문제다. #include #include #include using namespace std; vector solution(int m, int n, vector picture) { int number_of_area = 0; int max_size_of_one_area = 0; vector vis(101, vector(101, false)); queue 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++) { ..

문자 배열이 주어지면 각 자릿수로 만들 수 있는 모든 경우의 수를 따져서 소수가 되는 수가 몇 개인지 따져보는 문제다. 소수는 에라토스테네스의 체로 쉽게 구할 수 있지만 문제는 '어떻게 모든 경우의 수를 따지는가'이다. 우리는 두 가지 경우로 풀 수 있다. 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

참여자와 완주자 배열이 주어지면 완주하지 못한 선수의 이름을 리턴하면 되는 쉬운 문제다. 난 map을 이용해서 해결했는데 다른 사람의 풀이를 보니 두 배열을 정렬하고 이름이 같지 않다면 그 이름을 리턴해주는 식으로 풀었다. #include #include #include using namespace std; string solution(vector participant, vector completion) { string answer = ""; map m; for (auto i : participant) { m[i]++; } for (auto i : completion) { m[i]--; } for (auto i : participant) { if (m[i] == 1) answer = i; } return..