[leetcode]2222. Number of Ways to Select Buildings

문제

You are given a 0-indexed binary string s which represents the types of buildings along a street where:

s[i] = '0' denotes that the ith building is an office and
s[i] = '1' denotes that the ith building is a restaurant.
As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.

For example, given s = "001101", we cannot select the 1st, 3rd, and 5th buildings as that would form "011" which is not allowed due to having two consecutive buildings of the same type.
Return the number of valid ways to select 3 buildings.

예시

• Example 1:
  - Input: s = "001101"
  - Output: 6

• Example 2:
  - Input: s = "11100"
  - Output: 0

제한사항

3 <= s.length <= 105
s[i] is either '0' or '1'.

풀이1

/**
 * @param {string} s
 * @return {number}
 */
var numberOfWays = function (s) {
  const sArray = s.split('');
  const ans = [];
  let co = 0;
  function count(array, answer) {
    if (answer.length == 3) {
      co++;
      return;
    }
    for (let i = 0; i < array.length; i++) {
      if (!answer.length) {
        count(array.slice(i + 1), [array[i]]);
      } else {
        if (array[i] !== answer[answer.length - 1]) {
          count(array.slice(i + 1), [...answer, array[i]]);
        }
      }
    }
  }

  count(sArray, ans);
  return co;
};

처음에는 재귀함수를 통한 dfs방식을 생각했다. 그래서 answer의 answer[answer.length-1]과 다른 값이 들어오면 진행하고, answer.length ==3을 만족하게 되면 count를 하는 방식으로 recursive function을 구성했다.
제한사항의 s.length가 105였기 때문에, 당연히 TimeLimit Exceed의 결과가 나왔다.

풀이2

var numberOfWays = function (s) {
  const n = s.length;

  let validWays = 0;

  let postFixOnes = 0;
  let postFixZeros = 0;

  for (let i = 0; i < n; ++i) {
    const bit = s.charAt(i);

    if (bit === '1') ++postFixOnes;
    else ++postFixZeros;
  }

  let prefixOnes = 0;
  let prefixZeros = 0;

  for (let i = 0; i < n; ++i) {
    const bit = s.charAt(i);

    if (bit === '1') {
      --postFixOnes;
      validWays += prefixZeros * postFixZeros;
      ++prefixOnes;
    } else {
      --postFixZeros;
      validWays += prefixOnes * postFixOnes;
      ++prefixZeros;
    }
  }

  return validWays;
};

결과 값이 3개의 answer.length를 만족해야하는 것이기때문에, Sliding WIndows와도 비슷한 개념으로 문제를 풀이할 수 있었다.
for Loop를 돌리는 와중에 앞, 뒤로 나와 다른 value가 몇 개가 있는지 구해서 곱한 값들을 모두 더해주면 값을 구할 수 있었다.

그외

제한사항을 잘 확인하고, 어떤 알고리즘을 활용하거나 하기 전에 시간복잡도가 얼마나 될것인가, 이 제한사항이면 구현했을때 문제가 없을 것인가를 확인을 잘 해야겠다!