알고리즘 스터디 42주차 - [프로그래머스] 크기가 작은 부분 문자열, [LeetCode] Assign Cookies

1. 크기가 작은 부분 문자열 (Level 1)

Problem Summary

• 숫자로 이루어진 문자열인 t, p가 주어진다.
• t에서 p와 길이가 같은 부분 문자열 중, 부분 문자열이 나타내는 수가 p보다 작거나 같은 것이 몇 번 나오는지 횟수를 리턴한다.

Solution

function solution(t, p) {
    let answer = 0;
    const length = p.length;
    const pNum = Number(p)

    for (let i = 0; i <= t.length - length; i++) {
        const curNum = Number(t.slice(i, i + length));
        if (curNum <= pNum) answer++;
    }

    return answer;
}

• p의 길이를 구해 놓고, p를 숫자로 변환시켜 놓는다.
• 문자열 t를 순회한다.
  • 이때 범위는 0부터 t.length - p.length이다.
    • t가 “123456”이면 123, 234, 345, 456 이렇게 봐야 하기 때문
• t를 순회하면서 slice 메서드를 사용하여 p의 길이만큼 curNum을 추출해낸다.
• curNum이 pNum보다 작거나 같으면 answer를 추가한다.

Result

 

2. Assign Cookies (LeetCode Easy)

Problem Summary

• Give each child at most one cookie - 각 어린이마다 최대 하나의 쿠키를 줘야 함
• Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with.
• Each cookie j has a size s[j]
• If s[j] ≥ g[i], we can assign the cookie j to the child i, and the child i will be content.
• Goal: maximize the number of your content children and output the maximum number

Solution

var findContentChildren = function (g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => b - a);

  let answer = 0;

  for (let i = 0; i < g.length; i++) {
    if (!s.length) return answer;
    const child = g[i];

    while (s.length) {
      const cookie = s.pop();
      if (child <= cookie) {
        answer++;
        break;
      } else {
        continue;
      }
    }
  }

  return answer;
};

• Idea: 최대한 많은 아이를 만족 → 정렬해서 적은 쿠키를 원하는 아이부터 만족시키기
  • 아이는 오름차순, 쿠키는 내림차순(shift 대신 pop 하면서 하나씩 없앨 거라서)
• 현재 쿠키를 pop으로 뽑아 주고, child가 원하는 값과 같거나 큰지 비교한 후
  • 충족되면 answer를 증가시켜주고 break
  • 미충족되면 다시 pop으로 넘어가기

Another solution

• 참고 : https://leetcode.com/problems/assign-cookies/solutions/432753/javascript-greedy-faster-99-3-space-100/

var findContentChildren = function(g, s) {
    g = g.sort((a,b) => a-b)
    s = s.sort((a,b) => a-b)

    let i=0 // cookie index
    let count = 0;
    let j=0 // child index
    while(i<s.length){
        if(s[i] >= g[j]){
            count++
            j++
        }
        i++
    }

    return count
};

• pop 연산, 중첩된 while 문 등이 없기 때문에 좀 더 효율적인 풀이.
• i, j 인덱스를 0부터 따로 두고
  • 조건이 충족된다면 child의 인덱스를 올리고, 충족되지 않으면 cookie의 인덱스를 올리는 식으로 구현

Result