180. 크기가 작은 부분 문자열 Javascript

https://school.programmers.co.kr/learn/courses/30/lessons/147355

프로그래머스

 

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
  t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 구하라
  
• 주어진 자료는 무엇인가?
  숫자로 이루어진 문자열 t와 p
  
• 조건은 무엇인가?
  1 ≤ p의 길이 ≤ 18
  p의 길이 ≤ t의 길이 ≤ 10,000
  t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.
  

2. 계획

• p의 길이를 구한다.
• t에서 p의 길이 만큼 잘라서 새로운 배열에 넣는다. 
• 이 배열을 순회하면서 p보다 작거나 같은수가 있다면 count++해준다.

3. 실행

const solution = (t, p) => {
  //p의 길이를 구한다.
  const pLength = p.length;

  //t에서 p의 길이 만큼 잘라서 새로운 배열에 넣는다.
  let arr = [];
  for (let i = 0; i < t.length; i++) {
    let slice = t.slice(i, i + pLength);
    if (slice.length === pLength) {
      arr.push(slice);
    }
  }

  //이 배열을 순회하면서 p보다 작거나 같은수가 있다면 count++해준다.
  return arr.filter((it) => Number(it) <= Number(p)).length;
};

test('solution', () => {
  expect(solution("3141592", "271")).toEqual(2);
  expect(solution("500220839878", "7")).toEqual(8);
  expect(solution("10203", "15")).toEqual(3);
});

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
  재귀 혹은 while문을 사용해서 해결 할 수 있다.

재귀로 풀이는 가능하나 시간초과가 난다.

const solution = (t, p, count = 0) => {
  let slice = t.slice(0, p.length);

  if (t.length < p.length) {
    return count
  }

  if (Number(slice) <= Number(p)) count++

  return solution(t.slice(1), p, count)
}

 

while문을 사용한 풀이

const solution = (t, p) => {
  let tt = t;
  let count = 0;

  while (true) {
    if (tt.length < p.length) {
      return count
    }

    let slice = tt.slice(0, p.length);

    if (Number(slice) <= Number(p)) count++

    tt = tt.slice(1)
  }
}