LeetCode #455 AssignCookies. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
처음에 금방 푼 게 퍼포먼스가 너무 안 좋아서 중상 정도로 올리는데 시간 좀 걸림
병합정렬과 비슷한 방법이다.
First solution had too bad performance, so i spent some time for tunning to upper mid performance
It's similar with merge sort
LeetCode #455
Q.
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
네가 쩌는 부모라고 가정해보고, 아이들에게 쿠키를 주려고 한다. 하지만, 각 아이들에게 한 쿠키를 준다. 각 아이들 i 는 욕구변수 (g)i 가 있는데, 아이가 받을 쿠키의 최소 사이즈이다. 쿠키 사이즈 j 는 (s)j 이다. 만약 s(j) 값이 g(i) 값보다 크면, 그 쿠키는 아이 i 에게 줄 수 있다. 목표는 아이들이 원하는 최소 크기에 맞는 쿠키를 줄 수 있는 최대값을 구하는 것이다.
Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.
노트 :
욕구인자는 항상 양수이다.
한 아이에게 한 개 이상을 줄 수 없다.
e.g.
Example 1:
Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
Process
// Process
//1. Input s, and g vectors
//2. Sort them
//3. Iterate from begin to the end of s and g vectors
// 3.1. If s element is equal or bigger than g element
// 3.1.1. -> count iteration values(both)
// 3.1.2. -> count resultCount
// 3.2. If s element is smaller than g element
// 3.2.1. -> count s iteration value
// 처리과정
//1. s 와 g 배열을 입력받는다.
//2. 정렬한다.
//3. s 나 g 둘 중 하나가 끝날 때까지 반복한다.
// 3.1. s 의 값이 g 값보다 크거나 같으면
// 3.1.1. 반복변수 i j 둘다 센다.
// 3.1.2. 결과카운트 센다.
// 3.2. s 값이 g 값보다 작으면
// 3.2.1. s 의 반복변수만 센다.
//4. 결과카운트 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int resultCount = 0;
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0;
int j = 0;
while (i < g.size() && j < s.size())
{
if (s[j] >= g[i])
{
++i;
++j;
++resultCount;
}
else if (s[j] < g[i])
{
++j;
}
}
return resultCount;
}
};
int main(int argc, char *argv[]) {
std::vector<int> s = { 1, 1, 3, 5 };
std::vector<int> g = { 1, 2, 3 };
Solution sln;
cout << sln.findContentChildren(g, s) << endl;
}
Something else you might like...?
2019/03/04 - [Algorithm/Leet Code] - LeetCode #551 StudentAttendanceRecord1. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/03/07 - [Algorithm/Leet Code] - LeetCode #557 reverseWordsInAString3. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/03/10 - [Algorithm/Leet Code] - LeetCode #559 MaximumDepthOfN-aryTree. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/17 - [Algorithm/Leet Code] - LeetCode #415 AddStrings. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/15 - [Algorithm/Leet Code] - LeetCode #290 WordPattern. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/14 - [Algorithm/Leet Code] - LeetCode #283 MoveZeroes. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/13 - [Algorithm/Leet Code] - LeetCode #258 AddDigits. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/12 - [Algorithm/Leet Code] - LeetCode #136 SingleNumber. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/10 - [Algorithm/Leet Code] - LeetCode #171 ExcelSheetColumnNumber. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/09 - [Algorithm/Leet Code] - LeetCode #709 ToLowerCase. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/08 - [Algorithm/Leet Code] - LeetCode #400 NthDigit. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/03 - [Algorithm/Leet Code] - LeetCode #393 UTF-8 Validation. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/03 - [Algorithm/Leet Code] - LeetCode #398 RandomPickIndex. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/01 - [Algorithm/Leet Code] - LeetCode #905 SortArrayByParity. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/31 - [Algorithm/Leet Code] - LeetCode #593 ValidSquare. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/16 - [Algorithm/Leet Code] - LeetCode #217 ContainsDuplicate. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/21 - [Algorithm/Leet Code] - LeetCode #219 ContainsDuplicate2. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/22 - [Algorithm/Leet Code] - LeetCode #220 ContainsDuplicate3. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/23 - [Algorithm/Leet Code] - LeetCode #225 ImplementStackUsingQueue. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2018/10/19 - [Programming/Design Pattern ] - Design pattern - Prototype (디자인패턴 - 프로토타입) / Java C++ C#
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #60 sudoku. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #59 spiralNumbers. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/08 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #58 messageFromBinaryCode. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/07 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #57 fileNaming. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #56 digitsProduct. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #55 differentSquares. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2018/12/28 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 - (#9, Tell, Don't Ask)
2018/12/26 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 (1)
2019/01/14 - [Programming/Java] - 자바 메모리 누수 체크/확인/고치는 방법, Memory leak check/fix in Java application, cleanCode/좋은코드/oop/객체지향
2019/01/25 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(3)
2018/12/16 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(2)
2018/12/27 - [Life/Health care] - Milk-Thistle 밀크시슬 usage/side effects/dosage/fatigue/supplement,효능/부작용/성인,소아 용법/건강/피로회복/영양제
2018/12/26 - [Life/Health care] - Selenium 셀레늄 usage/side effects/dosage 효능/부작용/성인,소아 용법