JavaScript - Algorithm 부등호숫자 문제

 

문제설명 

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

• 최대 9개의 부등호(<, >)가 주어집니다. (9개까지 나올 수 있습니다. ">" or "<, >" or " < > <" 이런식으로 나올 수 있습니다.)
• 부등호의 좌우에는 0부터 9사이의 숫자가 한 번씩만 들어가야 합니다. (중복없이 한번씩만 나옵니다.)
• 부등호를 만족하는 숫자의 조합을 차례대로 이어 붙여 만든 정수를 부등호 수라고 한다. 

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

 

• 예를 들어 "<" 이것 하나만 나왔을 때는  최대 부등호 수인 "89"(8 < 9 만족) 와 최소 부등호 수인 "01"( 0 < 1만족)을 뺀 89 - 01 = 88이 정답이 됩니다. 
• 2번째 예를 들면 "< >" 이런 부등호를 입력 받았을 때 최대 부등호 수인  897 ( 8 < 9 < 7를 만족)에서 최소 부등호수인 021 (0 < 2 < 1)을 뺀 897 - 021 = 876이 정답이 됩니다. 
• 3번째 예를 들면 "> < >"  이 3개의 부등호를 입력 받았을 때 최대 부등호 수인 9786 ( 9 > 7 < 8 > 6 만족)에서 1032를 뺀 (1 > 0 < 3 > 2 ) 8,754가 정답이 됩니다. 

 

입력

인자 1 : signs

• string 타입의 공백을 사이에 둔 부등호 기호들
• signs.length는 17 이하 (최대 9개의 부등호 기호)

출력

• number 타입을 리턴해야 합니다.

주의사항

• 첫 자리가 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)

 

풀이코드 설명

다른 방식으로 풀 수도 있을 것 같은데 현재는 레퍼런스 코드를 이해하는 것만도 벅차다. 우선 이해가 안되서 console.log를 찍고 

흐름만 이해했다.

 

const inequalityNumber = function (signs) {
    const aux = (idx, signs, nums, digits, isVisited) => {

    console.log("idx",idx)

    //idx : 인덱스 
    //signs : 부등호
    //nums : [] 빈 배열 
    //digits : const digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; 
    //isVisited : 방문했는지 체크하는 boolean 
    // const min = aux(-1, signs, [], digits, Array(10).fill(false));
    // const max = aux(-1, signs, [], digits.reverse(), Array(10).fill(false));
      if (idx === signs.length) {
        // 부등호 수를 만든 경우
        console.log("idx",idx)
        return parseInt(nums.join(''));
      }
      

      const sign = signs[idx];
      console.log("sign",sign)
      for (let i = 0; i < digits.length; i++) {
        // 숫자를 차례대로 검토한다.
        // max를 구할 때는 9부터, min을 구할 때는 0부터
        const right = digits[i];
        console.log("right",right)

        //isVisited[right]가 true 면 스킵 
        // 이전 단계에서 사용한 숫자인 경우 스킵
        if (isVisited[right]) continue;
  
        // 첫번째 숫자가 아닌 경우에는 조건이 중요하다.
        // idx>=0이상일 경우 다음과 같이 적용

        if (idx >= 0) {
          // 항상 바로 직전의 숫자와 비교하면 된다.
          //left변수에 nums[nums.length-1]을 할당 
          const left = nums[nums.length - 1];
          console.log("left",left)

          //"sign은 < 고 left가 right 이상일 경우 반복문 탈출"
          //"sign은 > 고 right가 left 이상일 경우 반복문 탈출"
          if (sign === '<' && left >= right) continue;
          if (sign === '>' && left <= right) continue;
        }
  
        // 조건을 만족하거나 첫번째 숫자인 경우
        isVisited[right] = true;

        // 재귀 호출 target변수에 aux  재귀를 호출하되 
        //idx는 1추가, sign 그대로, nums 빈배열에 right를 더하기, digits, isVisited는 그대로 

        const target = aux(idx + 1, signs, nums.concat(right), digits, isVisited);
        console.log("target",target)
        console.log("nums",nums)
        if (target !== undefined) {
          // 부등호 수를 이미 찾은 경우 탐색을 더 할 필요가 없다.
          return target;
        }
        // 탐색에 실패한 경우, 시도한 숫자의 상태(사용중)를 원래대로(사용안함) 바꿔놔야 한다.
        isVisited[right] = false;
      }
  
      return undefined;
    };
    
    //문자열을 일정한 구분자로 잘라서 배열로 반환함 
    signs = signs.split(' ');
    console.log("signs",signs )

    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));
    
    console.log("max",max, "min",min)
    return max - min;
  };

 

 

 

console.log 출력 값 (1번 입출력만 계산함)

signs [ '<' ]
idx -1
sign undefined
right 0
idx 0
sign <
right 0
right 1
left 0
idx 1
idx 1
target 1
nums [ 0 ]
target 1
nums []
idx -1
sign undefined
right 9
idx 0
sign <
right 9
right 8
left 9
right 7
left 9
right 6
left 9
right 5
left 9
right 4
left 9
right 3
left 9
right 2
left 9
right 1
left 9
right 0
left 9
target undefined
nums []
right 8
idx 0
sign <
right 9
left 8
idx 1
idx 1
target 89
nums [ 8 ]
target 89
nums []
max 89 min 1
88