[Leetcode/C++] 455_Assign Cookies๐Ÿช

4964 ๋‹จ์–ด sortinggreedyleetcodegreedy

๋ฌธ์ œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

p1๋ฒˆ์งธ ์•„์ด๋Š” g[p1] ์ด์ƒ ํฌ๊ธฐ์˜ ์ฟ ํ‚ค๋ฅผ ๋ฐ›์•„์•ผ ํ•˜๊ณ , p2๋ฒˆ์งธ ์ฟ ํ‚ค์˜ ์‚ฌ์ด์ฆˆ๋Š” s[p2]์ž…๋‹ˆ๋‹ค.
์ด๋•Œ, g[p1]<=s[p2]์ผ ๋•Œ, ํ•ด๋‹น p1๋ฒˆ์งธ ์•„์ด์—๊ฒŒ ์ฟ ํ‚ค๋ฅผ ๋‚˜๋ˆ ์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ด ๋ฌธ์ œ๋Š” ๊ฐ€์žฅ ๋งŽ์€ ์•„์ด๋“ค์—๊ฒŒ ์ฟ ํ‚ค๋ฅผ ๋‚˜๋ˆ ์ฃผ๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์ œ๊ฐ€ ํ‘ผ ํ’€์ด ๊ณผ์ •์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.
๋จผ์ € ์ž…๋ ฅ๋ฐ›์€ ๋‘ ๋ฒกํ„ฐ g, s๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ ํ›„์— ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.
p1, p2 ์˜ ๋‘ ํฌ์ธํ„ฐ๋ฅผ ์„ค์ •ํ•˜์˜€๊ณ , ์‹œ์ž‘์ธ๋ฑ์Šค๋Š” 0์ด๋ฏ€๋กœ ๋‘ ํฌ์ธํ„ฐ ๋ชจ๋‘ 0๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.
์ฟ ํ‚ค๋ฅผ ๋ฐ›์€ ์•„์ด์˜ ์ˆ˜๋Š” ๋ณ€์ˆ˜ res๋กœ ๊ณ„์‚ฐํ–ˆ์Šต๋‹ˆ๋‹ค.
g[p1]<=s[p2]์ธ ๊ฒฝ์šฐ์—๋งŒ ์•„์ด์—๊ฒŒ ์ฟ ํ‚ค๋ฅผ ๋‚˜๋ˆ ์ค„ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์ด๊ณ , -> p1++; p2++; res++;
์ด ์™ธ์—๋Š” ์ฟ ํ‚ค๋ฅผ ๋‚˜๋ˆ ์ค„ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. -> p2++; (p2๋งŒ ํ•œ ์นธ ์ด๋™์‹œํ‚ค๊ธฐ)

  • g[p1]<=s[p2] : ์ฟ ํ‚ค ๋‚˜๋ˆ ์ค„ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ
  • g[p1]>s[p2] : ์ฟ ํ‚ค ๋‚˜๋ˆ ์ค„ ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ

์ „์ฒด ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end()); sort(s.begin(), s.end());
        
        int p1=0, p2=0, res=0;
        while(p1<g.size() && p2<s.size()){
            if(g[p1]<=s[p2]){
                p1++; p2++; res++;
            }
            else{
                p2++;
            }
        }
        
        return res;
    }
};

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ