0825 TIL Tree , JSON

🙆‍♀️JSON 구조가 재귀 함수를 사용할 수 있는 Tree 구조임을 이해할 수 있다. (stringifyJSON)

🙆‍♀️JSON.stringify 와 JSON.parse 가 seriealize, deserialize라는 것을 이해할 수 있다.

JSON.stringify : Object type을 JSON으로 변환 (serialized,직렬화)
JSON.parse : JSON을 Object type으로 변환 (deserialized,역직렬화)

🙆‍♀️JSON.stringify 와 JSON.parse 를 사용하여 자바스크립트 값과 JSON을 넘나들 수 있다.

🙆‍♀️JSON에 재귀 호출을 사용할 때, 어디에 사용해야 할지 이해할 수 있다.

null 타입은 객체이다. 버그라는 소리도 있는데, 이는 사실이 아니라고 한다. 보통 빈 객체를 만들 때 사용한다.

객체의 value 값이 undefined 또는 function(){}일 때, JSON.springify 메서드를 사용하면 {} 이 출력된다. 이를 다시 JSON.parse해도 원래 값으로 돌아가지 못하고 {}이 출력된다.

`[${[result]}]` 와 같은 식(`[${result}]`와 같다)을 활용해서 배열을 JSON 형태로 만들 수 있지만 추천되지 않는 방식이다. 문자열을 이용하는 것이 정석이라고 한다.

`${[1, 2]}`을 입력하면 배열이 풀려 “1,2”가 출력된다.

문자열을 조금 더 자유롭게 활용하기 위해서는 이스케이프 시퀀스를 찾아볼 수 있다. \n \', \"

DOM에 for문을 적용하면, 엘리먼트 생성 부분이 재선언 되는 것처럼 느껴지지만 반복문 종료와 함께 스코프가 종료되는 것이기 때문에 재선언되는 것이 아니다.

Array.fill() 메소드는 배열의 시작 인덱스부터 끝 인덱스의 이전까지 정적인 값 하나로 채운다.

TOY 1번

function orderOfPresentation(N, K) {
                 // 조의 개수 N, 발표 순서 K
  const factorial = (n) => {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
  };

  let order = 0; // 발표 순서를 담는 변수
  
  // N개의 조 중에, 어떠한 조가 이미 포함되었는지 확인하기 위해 배열을 만든다.
  // 만약 N이 3이라면 [false, false, false, false]
  // 제일 첫 번째는 더미 데이터(인덱스는 0부터 시작하지만 조는 1부터 시작하기 때문)
  const isUsed = Array(N + 1).fill(false);
  
  for (let i = 0; i < K.length; i++) {
    const num = K[i];
    // 사용했는지 판별하기 위해 isUsed에 체크합니다. (중복이 아니기 때문에)
    isUsed[num] = true;
    // num보다 앞에 올 수 있는 수들의 배열을 복제해서,
    const candidates = isUsed.slice(1, num);
    // 이 중에서 아직 사용되지 않은 수의 개수를 구합니다.
    const validCnt = candidates.filter((el) => el === false).length;
    // 아직 사용되지 않은 수, 그 전까지의 모든 경우의 수를 카운트합니다.
    const formerCnt = validCnt * factorial(N - i - 1);
    // order에 추가합니다.
    order = order + formerCnt;
  }
  
  return order;
}

돌아가는 과정

function orderOfPresentation(N,K) {
  //N = 5 , K = [3,5,4,2,1]
   const fatorial = (n) => {
		if(n <= 1) return 1;
	  return n * factorial(n - 1);
  }

  let order = 0;
    const isUsed = Array(N + 1).fill(false);
    // [false, false, false, false, false, false]
  
  for (let i = 0; i < K.length; i++) {
    const num = K[i]; //i = 0 , num = 3
    isUsed[num] = true; // [false, false, false, true, false, false]
    const candidates = isUsed.slice(1, num); //[false,false]
    const validCnt = candidates.filter((el) => el === false).length; // 2
    const formerCnt = validCnt * factorial(N - i - 1); //2 * 4!(=24) = 48
    order = order + formerCnt; //48
  
}
  
    const num = K[i]; //i = 1 , num = 5
    isUsed[num] = true; // [false, false, false, true, false, true]
    const candidates = isUsed.slice(1, num); //[false,false,true,false]
    const validCnt = candidates.filter((el) => el === false).length; // 3
    const formerCnt = validCnt * factorial(N - i - 1); //3 * 3!(=6) = 18
    order = order + formerCnt; //48 + 18 = 66
  
}
  
    const num = K[i]; //i = 2, num = 4
    isUsed[num] = true; // [false, false, false, true, true, true]
    const candidates = isUsed.slice(1, num); //[false,false,true]
    const validCnt = candidates.filter((el) => el === false).length; // 2
    const formerCnt = validCnt * factorial(N - i - 1); //2 * 2!(=2) = 4
    order = order + formerCnt; //66 + 4 = 70
  
}
  
    const num = K[i]; //i = 3, num = 2
    isUsed[num] = true; // [false, false, true, true, true, true]
    const candidates = isUsed.slice(1, num); //[false]
    const validCnt = candidates.filter((el) => el === false).length; // 1
    const formerCnt = validCnt * factorial(N - i - 1); //1 * 1! = 1
    order = order + formerCnt; // 70 + 1 = 71
  
}
  
    const num = K[i]; //i = 4, num = 1
    isUsed[num] = true; // [false, true, true, true, true, true]
    const candidates = isUsed.slice(1, num); //[]
    const validCnt = candidates.filter((el) => el === false).length; // 0
    const formerCnt = validCnt * factorial(N - i - 1); // 0 * 0 = 0
    order = order + formerCnt; // 71 + 0 = 0
  
}
 return order; // 71
}

느낀 점

요즘 너무 수도코드를 대충 쓰는것 같은데 다시 수도코드를 꼼꼼하게 작성해야할 것 같다.
재귀함수를 생각해내고 작성하는게 너무 어렵다. 토이도 재귀도 마음처럼 안되서 답답하다. 체력이 떨어져가는데 운동도 하고 최대한 쉬는 시간을 줄여야할 것같다.
반복만이 살 길이다.