문제 링크

Push Dominoes - LeetCode

문제 풀이

투포인터 알고리즘을 사용하여 풀었다.

투포인터 알고리즘은 크게 2가지 경우로 나누어 진행한다.

1. hi 가 R 을 만나는 경우
   • loArr 이라는 배열에 현재 hi(R 의 index)값을 저장해둔다.
2. hi 가 'L' 을 만나는 경우
   • 만약 loArr 이 비어있다면 가능한 계속 L 을 채운다
   • loArr 이 있다면 가장 최근에 추가된 1개를 제외하고 가능한 계속 R 을 채운다.
   • 마지막 1개의 R 이 남으면 L 과 동시에 값을 채운다.

이렇게 반복문이 끝나면 loArr 이 남아있는 경우까지 처리하면 끝이다.

나의 코드

var pushDominoes = function (dominoes) {
  let answer = dominoes.split("");
  const loArr = [];
  for (let hi = 0; hi < dominoes.length; ++hi) {
    if (dominoes[hi] === "R") loArr.push(hi);
    else if (dominoes[hi] === "L") {
      let right = hi - 1;
      if (!loArr.length) {
        while (right >= 0 && answer[right] === ".") answer[right--] = "L";
      } else {
        while (loArr.length > 1) {
          let start = loArr.shift() + 1;
          while (start < dominoes.length && answer[start] === ".")
            answer[start++] = "R";
        }
        let left = loArr.pop() + 1;
        while (left < right) {
          answer[left++] = "R";
          answer[right--] = "L";
        }
      }
    }
  }
  while (loArr.length) {
    let start = loArr.pop() + 1;
    while (start < answer.length && answer[start] === ".")
      answer[start++] = ["R"];
  }
  return answer.join("");
};