백준 1065번: 한수 - 등차수열 판별 문제

// 1~99는 모두 한수
// 따라서 N이 99 이하면 답은 N
if (N <= 99) {
  return N;
}

function isHansu(num) {
  // 1자리, 2자리는 모두 한수
  if (num < 100) {
    return true;
  }

  // 각 자리 숫자를 배열로 추출
  const digits = num.toString().split('').map(Number);
  // 예: 123 → "123" → ["1","2","3"] → [1,2,3]

  // 첫 번째 공차 계산
  // ㄴ 첫전째와 두번째 자리의 공차
  const difference = digits[1] - digits[0];

  // 모든 연속된 자리의 공차가 같은지 확인
  // ㄴ 반복문이 i = 2 부터 시작하는 이유:
  //    ㄴ digits[0]과 digits[1]의 공차는 이미 difference에 저장됨
  //    ㄴ 이제 digits[1]과 digits[2], digits[2]와 digits[3, ..확인 해야 함
  for (let i = 2; i < digits.length; i++) {
    if (digits[i] - digits[i - 1] !== difference) {
      return false; // 공차가 다르면 한수 아님
    }
  }

  return true; // 모든 공차가 같으면 한수
}

function countHansu(n) {
  let count = 0;

  for (let i = 1; i <= n; i++) {
    if (isHansu(i)) {
      count++;
    }
  }

  return count;
}

// 백준 1065번: 한수
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const N = parseInt(input);

/**
 * 주어진 숫자가 한수인지 확인
 * @param {number} num - 확인할 숫자
 * @returns {boolean} - 한수이면 true, 아니면 false
 */
function isHansu(num) {
  // 1자리 수와 2자리 수는 모두 한수
  if (num < 100) {
    return true;
  }

  // 숫자를 문자열로 변환하여 각 자리 숫자 추출
  const digits = num.toString().split('').map(Number);

  // 첫 번째 공차 계산
  const difference = digits[1] - digits[0];

  // 모든 연속된 자리수의 차이가 같은지 확인
  for (let i = 2; i < digits.length; i++) {
    if (digits[i] - digits[i - 1] !== difference) {
      return false;
    }
  }

  return true;
}

/**
 * 1부터 N까지의 한수 개수 세기
 * @param {number} n - 상한값
 * @returns {number} - 한수의 개수
 */
function countHansu(n) {
  let count = 0;

  for (let i = 1; i <= n; i++) {
    if (isHansu(i)) {
      count++;
    }
  }

  return count;
}

console.log(countHansu(N));

for (let i = 1; i <= n; i++) {          // O(N)
  if (isHansu(i)) {
    const digits = i.toString()...      // O(D) - 자릿수만큼
    for (let j = 2; j < digits.length)  // O(D)
  }
}

function countHansu(n) {
  // N이 99 이하면 모두 한수
  if (n < 100) {
    return n;
  }

  // 100 이상부터만 검사
  let count = 99; // 1~99는 모두 한수

  for (let i = 100; i <= n; i++) {
    if (isHansu(i)) {
      count++;
    }
  }

  return count;
}

/**
 * 한수를 직접 생성하는 방식
 * 시간 복잡도: O(D² × 19) where D는 최대 자릿수
 */
function countHansuOptimized(n) {
  if (n < 100) return n;

  let count = 99; // 1~99는 모두 한수
  const maxDigits = n.toString().length;

  // 3자리부터 maxDigits자리까지
  for (let digits = 3; digits <= maxDigits; digits++) {
    // 첫 자리 (1~9, 0으로 시작 불가)
    for (let first = 1; first <= 9; first++) {
      // 공차 (-9 ~ 9)
      for (let diff = -9; diff <= 9; diff++) {
        const num = generateHansu(first, diff, digits);

        // 유효한 한수이고 N 이하인 경우만 카운트
        if (num !== null && num <= n) {
          count++;
        }
      }
    }
  }

  return count;
}

/**
 * 첫 자리, 공차, 자릿수로 한수 생성
 * @returns {number|null} 유효하면 한수, 아니면 null
 */
function generateHansu(first, diff, digitCount) {
  let num = first;
  let current = first;

  for (let i = 1; i < digitCount; i++) {
    current += diff;

    // 각 자리는 0~9 범위여야 함
    if (current < 0 || current > 9) {
      return null;
    }

    num = num * 10 + current;
  }

  return num;
}

// 3자리 한수 생성
// first=1, diff=2, digits=3
// → 1 → 1+2=3 → 3+2=5 → 135 ✅

// first=1, diff=5, digits=3
// → 1 → 1+5=6 → 6+5=11 (범위 초과) → null ❌

// first=9, diff=-1, digits=4
// → 9 → 8 → 7 → 6 → 9876 ✅

function isHansuSpaceOptimized(num) {
  if (num < 100) return true;

  // 마지막 두 자리로 첫 공차 계산
  let prev = num % 10;
  num = Math.floor(num / 10);
  let current = num % 10;
  const diff = current - prev;

  // 나머지 자리 검사
  while (num >= 10) {
    prev = current;
    num = Math.floor(num / 10);
    current = num % 10;

    if (current - prev !== diff) {
      return false;
    }
  }

  return true;
}

// ❌ 잘못된 코드
function isHansu(num) {
  const digits = num.toString().split('').map(Number);
  const difference = digits[1] - digits[0];

  for (let i = 2; i < digits.length; i++) {
    // ...
  }
}

// 문제: 1자리 수는 digits[1]이 undefined!
// 7 → digits = [7] → digits[1] = undefined → difference = NaN

// 111은 한수일까?
// 각 자리: 1, 1, 1
// 공차: 0, 0 → 모든 공차가 0으로 같으므로 한수! ✅

// ❌ 잘못된 코드
const digits = num.toString().split(''); // ["1", "2", "3"]
const difference = digits[1] - digits[0]; // "2" - "1" = 1 (우연히 작동)

// 하지만 명시적으로 숫자 변환하는 것이 좋음
const digits = num.toString().split('').map(Number); // [1, 2, 3]

// 테스트 함수
function test() {
  const testCases = [
    { input: 110, expected: 99 },
    { input: 1, expected: 1 },
    { input: 210, expected: 105 },
    { input: 1000, expected: 144 },
    { input: 500, expected: 119 },
  ];

  testCases.forEach(({ input, expected }) => {
    const result = countHansu(input);
    const pass = result === expected ? '✅' : '❌';
    console.log(`${pass} Input: ${input}, Expected: ${expected}, Got: ${result}`);
  });
}

test();