Algorithm problem-21

1. 문제

• 주어진 부등호에 만족하는 부등호 수를 만들어서 리턴하라
• 최대 9개의 부등호가 주어짐
• 부등호 좌,우에는 0~9의 숫자가 1번씩만 들어감
• 그 수를 차례대로 이어붙인 정수를 부등호 수라고 함

2. 시도

• 사실 문제를 이해하지 못했다
• 원하는 조건에 맞추어 코드를 어거지로 짜보긴 하였으나, 실패
• 차후에 다시 풀어서 덧붙이록 할 예정

3. 수도코드

const inequalityNumber = function (signs) {
  let max = [];
  let min = [];
  let numMin = [0,1,2,3,4,5,6,7,8,9]
  let numMax = [9,8,7,6,5,4,3,2,1,0]
  for (let i = 0; i < signs.length; i++) {
    if (signs[i] === '>' && numMax[i] > numMax[i+1]) {
      max.push(numMax[i])
      max.push(numMax[i+1])
      console.log(max)
    } else {
      max.push(numMax[i+1])
      max.push(numMax[i])
      console.log(max)
    }
  }
  for (let i = 0; i < signs.length; i++) {
    if (signs[i] === '>' && numMin[i] > numMin[i+1]) {
      min.push(numMin[i+1])
      min.push(numMin[i])
      console.log(min)
    } else {
      min.push(numMin[i])
      min.push(numMin[i+1])
      console.log(min)
    }
  }
  return max
};

4. 레퍼런스

const inequalityNumber = function (signs) {
  const aux = (idx, signs, nums, digits, isVisited) => {
    if (idx === signs.length) {
      // 부등호 수를 만든 경우
      return parseInt(nums.join(''));
    }

    const sign = signs[idx];
    for (let i = 0; i < digits.length; i++) {
      // 숫자를 차례대로 검토한다.
      // max를 구할 때는 9부터, min을 구할 때는 0부터
      const right = digits[i];
      // 이전 단계에서 사용한 숫자인 경우 스킵
      if (isVisited[right]) continue;

      // 첫번째 숫자가 아닌 경우에는 조건이 중요하다.
      if (idx >= 0) {
        // 항상 바로 직전의 숫자와 비교하면 된다.
        const left = nums[nums.length - 1];
        if (sign === '<' && left >= right) continue;
        if (sign === '>' && left <= right) continue;
      }

      // 조건을 만족하거나 첫번째 숫자인 경우
      isVisited[right] = true;
      const target = aux(idx + 1, signs, nums.concat(right), digits, isVisited);
      if (target !== undefined) {
        // 부등호 수를 이미 찾은 경우 탐색을 더 할 필요가 없다.
        return target;
      }
      // 탐색에 실패한 경우, 시도한 숫자의 상태(사용중)를 원래대로(사용안함) 바꿔놔야 한다.
      isVisited[right] = false;
    }

    return undefined;
  };

  signs = signs.split(' ');
  const digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
  // arr.reverse()는 in-place 함수(데이터 직접 변경)이므로 min과 max의 순서는 중요하다.
  const min = aux(-1, signs, [], digits, Array(10).fill(false));
  const max = aux(-1, signs, [], digits.reverse(), Array(10).fill(false));
  return max - min;
};