Problem Solving/Leet Code (15) 썸네일형 리스트형 1706 Where Will the Ball Fall 이 문제도 조금 색다르긴 한데 어쨌든 전형적인 DFS 문제이다. C++ 더보기 class Solution { public: vector findBall(vector& grid) { vector res(grid[0].size()); for(size_t i = 0; i < res.size(); ++i){ size_t j = i, s = 0; while(res[i] == 0 && s < grid.size()){ if(grid[s][j] == 1){ if (j == res.size() - 1 || grid[s][j + 1] == -1) res[i] = -1; else{ ++j; ++s; } } else if (grid[s][j] == -1){ if (j == 0 || grid[s][j - 1] == 1) res.. 1705 Maximum Number of Eaten Apples 이 문제는 먼저 썩는 사과 먼저 먹어야 하는 전형적인 우선순위 큐 문제이다. C++ 더보기 class Solution { public: int eatenApples(vector& apples, vector& days) { using mypair = pair; priority_queue pq; int cnt{}; size_t i; for(i = 0; i < apples.size() || !pq.empty(); ++i){ while(!pq.empty() && pq.top().first 0) pq.push(top); } else{ int offset = min(top.first - int(i), top.second); cnt += offset; i += offset - 1; } } } return cnt; }.. 1704 Determine if String Halves Are Alike 이 문제는 주어진 문자열을 이등분한 후, 각 문자열에 포함된 모음의 수가 같으면 true를 반환하는 문제다 별다른 거 할 필요 없이 문제 그대로 구현하면 된다. C++ 더보기 class Solution { public: bool halvesAreAlike(string s) { map score; score['a'] = 1; score['e'] = 1; score['i'] = 1; score['o'] = 1; score['u'] = 1; score['A'] = 1; score['E'] = 1; score['I'] = 1; score['O'] = 1; score['U'] = 1; int a = 0, b = 0; for(size_t i = 0; i < s.length() / 2; ++i) a += score[.. 1713 Minimum Operations to Make a Subsequence 이 문제는 주어진 배열 arr이 target을 subsequence로 만드는 배열로 되려면 몇 번의 insert를 수행해야 하는지를 묻는 문제이다. 최장 공통부분 배열로 생각하기 쉽지만 아쉽게도 그렇게 풀면 시간 초과가 걸린다. 그래서 이 문제는 주어진 배열 arr이 문자열이 아니라 숫자로 구성되어 있으며, target의 원소가 모두 1번만 나타난 것에 유의해서 최장 증가 부분 수열로 풀어야 한다. =============================== 여담으로 포스팅한 1710부터 1713까지는 위클리 콘테스트 222의 문제이다. 이 콘테스트 1등이 23분만에 다 풀었는데 이쯤 되면 ICPC 올솔 할 수 있으려나 ㅋㅋㅋㅋㅋㅋ C++ 더보기 class Solution { public: int minOp.. 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 다음
