Leet Code (11) 썸네일형 리스트형 1712 Ways to Split Array Into Three Subarrays 숫자로 구성된 배열을 각각 mid의 합은 left의 합보다 같거나 크게, right의 합은 mid의 합보다 같거나 크게 3조각으로 나눌 수 있는 경우의 수를 구하는 문제이다. 이 문제는 정렬된 배열에서 특정한 값을 찾는 전형적인 이진 탐색 문제로, 누적합이 저장된 배열을 만들고, 그 배열에서 mid가 될 수 있는 최소 인덱스와 최대 인덱스를 찾으면 된다. 그리고 이진 탐색 말고도, 투 포인터로 풀린다. 나도 처음에 이진 탐색 말고도, 투 포인터로 하려고 했는데 예외 처리에서 애먹어서 그냥 이진 탐색으로 풀었다. 코드는 Discuss 뒤지면 나온다. C++ 더보기 class Solution { public: int waysToSplit(vector& nums) { vector sum(nums.size()).. 1711 Count Good Meals 입력으로 주어진 음식들 중에서 두 개를 선택했을 때, 맛있는 정도의 합이 2의 지수가 되는 경우의 수를 찾는 문제이다. 문제를 봤을 때, 바로 조합을 이용하는 방법이 생각났지만, 시간 복잡도 상 당연히 조합은 안 되었다. 그래서 일단 맛있는 정도를 Key, 등장 횟수를 value로 하는 해쉬맵을 만들고, 해당 해쉬맵을 순회하면서 모든 경우의 수를 찾는 시간복잡도 O(N)의 방법으로 해결했다. 여담으로 리트코드 채점 서버가 좀 이상한 거 같다. 같은 코드를 제출해도 수행시간이 2배까지도 차이가 났다... 음... 백준처럼 채점 서버에 제출이 몰리면 순차적으로 수행하는 게 아니라 그냥 동시에 돌리는 건가 C++ 더보기 class Solution { public: int countPairs(vector& de.. 1710 Maximum Units on a Truck Easy 난이도의 문제로 난이도대로 정말 쉽다 정렬만 해주면 바로 끝나는 문제이다. C++ 더보기 class Solution { public: int maximumUnits(vector& boxTypes, int truckSize) { auto f = [](vector b1, vector b2){return b1[1] > b2[1];}; sort(boxTypes.begin(),boxTypes.end(),f); int cnt{}; for(auto b : boxTypes){ if (truckSize>= b[0]){ truckSize -= b[0]; cnt += b[0] * b[1]; } else{ cnt += b[1] * truckSize; return cnt; } } return cnt; } }; Pyth.. 이전 1 2 다음
