Toy 문제 21

문제

아래와 같은 과정을 거쳐 부등호 수(inequalityNumber)를 만들 수 있습니다.

• 최대 9개의 부등호(<, >)가 주어집니다.
• 부등호의 좌우에는 0부터 9사이의 숫자가 한 번씩만 들어가야 합니다.
• 부등호를 만족하는 숫자의 조합을 차례대로 이어 붙여 만든 정수를 부등호 수라고 한다.

부등호 기호들을 입력받아 부등호를 만족하는 최대 부등호 수와 최소 부등호 수의 차이를 리턴해야 합니다.

주의사항

• 첫 자리가 0인 경우도 부등호 수에 포함되어야 합니다.
• 모든 입력에 답은 항상 존재합니다.

입출력 예시

let output = inequalityNumber('<');
console.log(output); // --> 88 (89 - 01)

output = inequalityNumber('< >');
console.log(output); // --> 876 (897 - 021)

output = inequalityNumber('> < >');
console.log(output); // --> 8,754 (9,786 - 1,032)

 

수도코드(해석)

문제 설명이 굉장히 별로여서 정리를 하자면, 숫자를 나열 하여 어떠한 수를 만들었을 때 그 숫자 자리 사이사이마다 부등호가 들어가서 그 부등호 식이 만족해야 하는 경우입니다.

 

부등호가 <, > 라고 주어 졌을 때

큰 값은 8<9>7 로 897이 되고

작은 값은 0<2>1 로 021이 되면서

두 값의 차이를 리턴 해야 합니다.

 

그리고 큰 값을 구할 때에는 9부터 사용을 하고, 작은 값을 구할 때에는 0부터 사용해야 합니다.

 

코드

레퍼런스 코드에 분석해서 설명을 붙였습니다. 크게 어려운 문법내용은 없지만 새로운 유형의 문제여서 까다로웠습니다.

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을 구할 때는 digits 배열을 리버스 해서 0부터 숫자를 차례로 검토하고
      const right = digits[i];
      // rigth 변수에 숫자를 넣고, 이전 단계에서 사용한 숫자인 경우 pass
      if (isVisited[right]) continue;

      // 첫번째 숫자가 아니고 부등호 조건이 만족하지 않을 경우
      if (idx >= 0) {
        // 항상 바로 직전의 숫자(nums는 사용했던 숫자)와 비교하면 된다.
        const left = nums[nums.length - 1];
        // 부등호의 조건이(부등호의 종류 2가지) 성립 하지 않으면 pass
        if (sign === '<' && left >= right) continue;
        if (sign === '>' && left <= right) continue;
      }

      // 위 조건에 해당하지 않는 경우 해당 숫자가 조건에 만족하는 이유 임으로 (조건을 만족하거나 첫번째 숫자인 경우)
      // 선택한 숫자를 true로 고치고
      isVisited[right] = true;
      
      // 선택한 숫자를 nums에 포함하여 재귀함수를 사용 한다.
      const target = aux(idx + 1, signs, nums.concat(right), digits, isVisited);

      // 부등호 수를 이미 찾은 경우 탐색을 더 할 필요가 없습니다.
      if (target !== undefined) {
        return target;
      }

      // 탐색에 실패한 경우, 시도한 숫자의 상태(사용중)true를 원래대로(사용안함)false로 수정
      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;
};

 

- inx가 -1로 시작하는 이유는 첫 숫자를 넣을 때에는 부등호가 필요 없기 때문입니다.

 

- 재귀함수를 사용하면서 그 안에 반복문을 넣었는데, 처음에 생각 할 때에는 코드를 줄일 수 있다고 생각 하였습니다. 하지만 잘못된 생각이었습니다.

예를들어 max라는 숫자를 출력 할 때 무조건 앞에 9가 나올 수 없는 경우도 존재하기에

9를 제일 처음에 선택을하고 재귀에 들어가게 됩니다. 재귀에 들어간다 해도 9보다 더 큰 수는 존재하지 않기 때문에 재귀에 자연스럽게 빠져나오고 9를 사용하지 않는 false로 바꾸고 첫 숫자를 8로 선택하고 다시 재귀로 들어가는 방식입니다.

 

또 이런 구조를 사용하는 이유는 숫자를 제일 먼저 선택해야하는 문제의 경우상 그렇습니다. 그래야만 부등호 숫자 부등호 숫자를 번갈아 가며 비교하여 대입할 수 있기 때문입니다.