Level 2. 문자열 압축 압축할 수 있는 모든 경우의 수를 찾아 실제 압축을 진행해 해결했다. 문자열의 길이가 4라면, 3개 단위부터는 압축이 불가능하므로 확인하지 않아도 된다. 벡터에 n 길이로 잘린 문자열들을 담은 후, 앞에서부터 동일한 문자열의 개수를 찾아 압축 문자열에 추가한다. 마지막 문자열 처리를 위해 쓰레기 값인 "0"을 추가해줬다. #include #include #include #include using namespace std; string compress(string& s, int n) { vector v; for (int pos = 0; pos < s.length(); pos += n) v.emplace_back(s.substr(pos, n)); v.emplace_back("0"..

Level 2. 124 나라의 숫자 십집수와 비교하며 패턴을 찾으면 된다. 124 나라에서는 십집수를 3으로 나눈 나머지가 0일 때 4, 4일 때 1, 2일 때 2가 된다. 124 나라에서 n자릿수로 바뀌는 십집수를 f(n)이라고 할 때, f(0) = 0 f(n) = 3ⁿ⁻¹ + f(n - 1) #include #include using namespace std; string solution(int n) { string answer; while (n) { int mod = n % 3; (n /= 3) -= (mod == 0); answer += "412"[mod]; } reverse(answer.begin(), answer.end()); return answer; }

Level 2. 가장 큰 정사각형 찾기 모든 점을 확인하며 가장 큰 정사각형을 찾기 때문에, 중복으로 인해 시간 초과가 발생했다. // 이 풀이는 시간 초과가 발생한다. #include #include #include using namespace std; int checkSquare(vector& board, int r, int c) { int n = 0; int R = board.size(), C = board.front().size(); while (r < R && c < C) { for (int i = r - n; i

Level 2. 게임 맵 최단거리 처음엔 DFS를 시도해 시간 초과가 발생했다. 내가 왔던 방향이 아닌 방향으로 계속 진행하면서 최소 비용을 갱신하는 방식이다. // 이 풀이는 시간 초과가 발생한다. #include #include #include #include using namespace std; enum class DIR { Up = 1, Down = 2, Left = 4, Right = 8 }; void rDFS(vector& maps, int i, int j, int from, int cost) { int n = maps.size(), m = maps.front().size(); if (i < 0 || n

Level 0. 간단한 논리 연산 #include using namespace std; bool solution(bool x1, bool x2, bool x3, bool x4) { return (x1 | x2) & (x3 | x4); }

Level 2. 줄 서는 방법 next_permutation() 함수로 간단하게 해결하면 시간 초과가 발생한다. // 이 풀이는 시간 초과가 발생한다. #include #include #include #include using namespace std; vector solution(int n, long long k) { vector answer(n); iota(answer.begin(), answer.end(), 1); while (--k) next_permutation(answer.begin(), answer.end()); return answer; } #include #include #include using namespace std; long long factorial(int n) { return (n