Level 2. 구명보트 배낭 문제에서 남는 공간을 최소화하기 위해서는 부피가 큰 물건부터 넣어야 하듯이, 이 문제에서도 몸무게가 많이 나가는 사람부터 보트에 태워야 한다. 앞뒤에서 삭제가 빈번하므로, vector 대신 deque을 사용했다. #include #include #include #include using namespace std; int solution(vector people, int limit) { int answer = 0; deque deq(people.begin(), people.end()); sort(deq.begin(), deq.end()); do { int total = limit; bool bSuccess = false; while (!deq.empty() && (deq.ba..

Level 2. N개의 최소공배수 아래처럼 최대공약수를 이용해 계산하면 [2, 3, 4]를 대입할 때 오답이 나온다. // 이 풀이는 틀린 풀이다. #include #include #include #include using namespace std; int GCD(int a, int b) { return b ? GCD(b, a % b) : a; } int solution(vector arr) { int gcd = arr[0]; for (int i = 1; i < arr.size(); ++i) gcd = GCD(gcd, arr[i]); return accumulate(arr.begin(), arr.end(), 1, ::multiplies()) / pow(gcd, arr.size() - 1); } 순서대로 ..

Level 0. 글자 지우기 indices의 원소 범위가 주어지지 않아. 배열 대신 unordered_map을 사용했다. 문자열을 붙이게 되면 메모리 재할당이 빈번하게 발생하므로, 미리 크기를 할당해놓고 사용했다. #include #include #include using namespace std; string solution(string my_string, vector indices) { size_t len = my_string.length(), size = indices.size(); string answer(len - size, '\0'); unordered_map umap; for (int index : indices) umap[index] = true; for (int i = 0, j = 0; ..

Level 0. 문자열이 몇 번 등장하는지 세기 #include using namespace std; int solution(string myString, string pat) { int answer = 0; size_t len = myString.length(), lenPat = pat.length(); for (int i = 0; i

Level 0. 문자열 겹쳐쓰기 #include #include using namespace std; string solution(string my_string, string overwrite_string, int s) { move(overwrite_string.begin(), overwrite_string.end(), my_string.begin() + s); return my_string; } #include using namespace std; string solution(string my_string, string overwrite_string, int s) { return my_string.replace(s, overwrite_string.length(), overwrite_string); }

Level 0. 수열과 구간 쿼리 2 정렬하지 않고 순회하면서 k보다 큰 원소들에 대해서만 최솟값을 구하면 한 쿼리당 O(n) 시간에 해결할 수 있다. #include #include #include using namespace std; vector solution(vector arr, vector queries) { size_t size = queries.size(); vector answer(size); for (int i = 0; i < size; ++i) { int t_min = 1'000'001; for (int j = queries[i][0]; j