알고리즘/Hacker Rank
-
[hacker rank] The bomberman game알고리즘/Hacker Rank 2021. 9. 10. 21:32
문제 링크 풀이 주어진 예제로 테스트 해보면 주기를 구할 수 있습니다. 3, 7, 11초..에 그리드의 형태가 같고, 5, 9, 13초..에 그리드의 형태가 같습니다. 첫 번째 주기는 폭발이 한 번 일어날 때며 두 번째 주기는 폭발이 두 번 일어날 때입니다. 이 규칙을 이용해 n의 크기를 줄여주면 됩니다. 코드 vector bomberMan(int n, vector grid) { vector pos; if (0 == n % 2) { for (size_t i = 0; i < grid.size(); ++i) for (size_t j = 0; j < grid[i].size(); ++j) grid[i][j] = 'O'; return grid; } else if ((n + 1) % 4 == 0) n = 3; el..
-
[hacker rank] The grid search알고리즘/Hacker Rank 2021. 9. 10. 10:41
문제 링크 풀이 그리드 배열에서 패턴 배열의 첫 번째 요소과 일치하는 문자열의 위치를 찾을 때마다 나머지 패턴을 비교했습니다. 패턴 배열의 첫 번째 요소와 일치하는 그리드 배열의 행의 위치가 패턴 배열의 크기보다 작으면 탐색을 멈춥니다. 탐색을 멈출 때까지 return이 이뤄지지 않았다면 그리드 배열에서 패턴을 찾지 못한 것입니다. 코드 string gridSearch(vector G, vector P) { for (size_t i = 0; i G.size() - P.size()) break; size_t col = 0; while (true) { col = G[i].find(P[0], col); if (string::npos == col) break; e..
-
[hacker rank] The time in words알고리즘/Hacker Rank 2021. 9. 9. 22:29
문제 링크 코드 string timeInWords(int h, int m) { std::string time[] = { "o' clock", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "tweleve", "thirteen", "fourteen", "quarter", "sixteen", "seventeen", "eighteen", "nineteen", "twenty" }; const int size = 40; char buf[size] = {}; if (0 == m) snprintf(buf, size, "%s %s", time[h].c_str(), time[m].c_str()); else i..
-
[hacker rank] Encryption알고리즘/Hacker Rank 2021. 9. 9. 13:10
문제 링크 풀이 문제에 나와 있는 암호화 방법대로 풀면 됩니다. 루트 값을 올림한 수와 내림한 수의 곱이 원래의 수보다 작다면 작은 쪽에 1을 더해주면 됩니다. 마지막에 각 로우의 한 글자씩만을 문자열에 담을 때는 반복문 칼럼의 인덱스가, 접근하는 문자열보다 크면 안 됩니다. 코드 string encryption(string s) { while (s.find(" ") != (size_t)-1) s.replace(s.find(" "), 1, ""); size_t length = s.size(); size_t row = floor(sqrtf(length)); size_t column = ceil(sqrtf(length)); if (row * column < length) ++row; vector str; s..
-
[hacker rank] Organizing containers of balls알고리즘/Hacker Rank 2021. 9. 8. 14:25
문제 링크 풀이 현재 각 컨테이너에 있는 공의 개수와, 각 타입별 공의 개수를 비교해봅니다. 현황이 일치하면 됩니다. 예를 들어 컨테이너에 들어 있는 공 개수 배열이 {3, 2, 3}이고, 각 타입에 대한 개수 배열이 {2, 3, 3}이면 서로 계속 스왑을 한다고 해도 컨테이너에 들어 있는 공의 현황이 {3, 2, 3}인 건 바뀌지 않습니다. 때문에 개수에 대한 현황이 같기만 하다면, 스왑을 하다 보면 각기 다른 컨테이너에 같은 타입의 공을 모을 수 있습니다. 코드 string organizingContainers(vector container) { size_t size = container.size(); vector each_container(size, 0); vector each_type(size, ..
-
[hacker rank] Extra long factorial알고리즘/Hacker Rank 2021. 9. 7. 19:02
문제 링크 풀이 배열 요소에 하나에 한 자리씩 넣어서 표현하면 됩니다. 올림 수는 그다음 배열로 넘기면 됩니다. 올림 수를 다음 배열로 넘겨야 하는데 배열의 공간이 부족할 때는, push_back(0)을 하여 0을 임시값으로 넣어주고 배열 공간을 늘립니다. 코드1 #include #include using namespace std; int main() { int N = 25; vector answer; answer.push_back(1); // number to multifly for (int i = 2; i
-
[hacker rank] Climbing the leaderboard알고리즘/Hacker Rank 2021. 9. 4. 13:49
문제 링크 풀이 쉽게 풀면 시간 복잡도가 O(N^2)으로 나오는데 실행 시간 초과로 통과되기 어려울 것입니다. 주어진 ranked 배열은 내림차순으로 정렬 되어 있고 player 배열은 오름차순입니다. 따라서 player 배열의 마지막부터 올라가면서 점수 별 player의 순위를 구하면 player 배열은 1번만 순회해도 되기 때문에 O(N)으로 문제를 풀 수 있습니다. 구하는 순위는 상승하기만 하므로 매번 처음부터 새로 구할 필요가 없기 때문입니다. 코드1 vector climbingLeaderboard(vector ranked, vector player) { int N = ranked.size(); int M = player.size(); int my_rank = 1; for (size_t i = 0..
-
[hacker rank]알고리즘/Hacker Rank 2021. 9. 1. 14:56
문제 링크 풀이 마방진을 알아야 풀 수 있는 문제입니다. 영어로 magic square입니다. 문제에선 3 x 3 마방진만 주어지는데요. 마방진은 가로, 세로, 대각선의 합이 모두 같습니다. 3 x 3에서는 그 합이 15입니다. 이미 문제에 하나가 주어져 있죠. 이걸 90도로 세 번 돌리고, 좌우/상하 대칭, 대각선 대칭해서 총 여덟 개의 경우의 수를 직접 구했습니다. 그러고 나서 주어지는 문제의 차이가 가장 적은 값을 찾으면 됩니다. 마방진이 무엇인지 알고 있었다면 빨리 풀 수 있는 문제입니다. 코드 #include int abs(int v) { return v < 0 ? -v : v; } int min(int a, int b) { return a < b ? a : b; } int main() { in..