핵심 알고리즘 가이드

// 😰 비효율적인 접근
function findDuplicates(arr) {
  const duplicates = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j] && !duplicates.includes(arr[i])) {
        duplicates.push(arr[i]);
      }
    }
  }
  return duplicates; // O(n³) 시간 복잡도!
}

// ✅ 효율적인 접근
function findDuplicates(arr) {
  const seen = new Set();
  const duplicates = new Set();

  for (const item of arr) {
    if (seen.has(item)) {
      duplicates.add(item);
    } else {
      seen.add(item);
    }
  }

  return Array.from(duplicates); // O(n) 시간 복잡도!
}

// ❌ 비효율적 (최적화 없음)
const bubbleSortBasic = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
};

// ✅ 최적화된 버전
const bubbleSort = (arr) => {
  let swapped;

  for (let i = 0; i < arr.length; i++) {
    swapped = false;

    // 이미 정렬된 부분은 제외
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    // 교환이 없었다면 이미 정렬됨
    if (!swapped) break;
  }

  return arr;
};

// 실사용 예시: 소규모 우선순위 목록 정렬
const priorityTasks = [
  { name: 'Task A', priority: 3 },
  { name: 'Task B', priority: 1 },
  { name: 'Task C', priority: 2 }
];

bubbleSort(priorityTasks, (a, b) => a.priority - b.priority);

// ❌ 큰 배열에는 사용하지 마세요!
const largeArray = Array.from({ length: 10000 }, () => Math.random());
bubbleSort(largeArray); // 너무 느림!

// ✅ 큰 배열은 퀵소트나 내장 sort() 사용
largeArray.sort((a, b) => a - b);

// ❌ 최악의 경우: 이미 정렬된 배열 + 나쁜 피벗 선택
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9];
// 항상 첫 번째 요소를 피벗으로 선택하면 O(n²)!

// ✅ 해결책 1: 랜덤 피벗 선택
const pivot = arr[Math.floor(Math.random() * arr.length)];

// ✅ 해결책 2: 중간값 피벗 선택 (median-of-three)
const mid = Math.floor(arr.length / 2);
const pivot = [arr[0], arr[mid], arr[arr.length - 1]]
  .sort((a, b) => a - b)[1];

// ✅ 해결책 3: 최악의 경우도 보장이 필요하면 병합 정렬 사용

// 외부 정렬 (대용량 파일 정렬)
const mergeSort = (arr) => {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
};

const merge = (left, right) => {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
};

// ❌ 정렬되지 않은 배열에서 이진 탐색
const unsorted = [5, 2, 8, 1, 9];
binarySearch(unsorted, 2); // 잘못된 결과!

// ✅ 먼저 정렬하거나 선형 탐색 사용
unsorted.sort((a, b) => a - b);
binarySearch(unsorted, 2); // 올바른 결과

// ❌ 중간값 계산 시 오버플로우 (매우 큰 배열)
const mid = (left + right) / 2; // left + right가 오버플로우 가능

// ✅ 안전한 중간값 계산
const mid = left + Math.floor((right - left) / 2);
// 또는
const mid = Math.floor((left + right) / 2); // JavaScript는 안전

// 1. 첫 번째 발견 위치 찾기
const findFirst = (arr, target) => {
  let left = 0, right = arr.length - 1, result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      result = mid;
      right = mid - 1; // 더 왼쪽도 확인
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
};

// 2. 마지막 발견 위치 찾기
const findLast = (arr, target) => {
  let left = 0, right = arr.length - 1, result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      result = mid;
      left = mid + 1; // 더 오른쪽도 확인
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
};

// 예시: [1, 2, 2, 2, 3, 4]에서 2 찾기
findFirst([1, 2, 2, 2, 3, 4], 2);  // 1
findLast([1, 2, 2, 2, 3, 4], 2);   // 3

// 파일 시스템 탐색
class FileSystem {
  constructor(name, isDirectory = false) {
    this.name = name;
    this.isDirectory = isDirectory;
    this.children = [];
  }

  addChild(node) {
    this.children.push(node);
  }
}

const dfsTraversal = (node, callback, depth = 0) => {
  callback(node, depth);

  if (node.isDirectory) {
    for (const child of node.children) {
      dfsTraversal(child, callback, depth + 1);
    }
  }
};

// 사용 예시
const root = new FileSystem('/', true);
const documents = new FileSystem('Documents', true);
const file1 = new FileSystem('file1.txt', false);

root.addChild(documents);
documents.addChild(file1);

dfsTraversal(root, (node, depth) => {
  console.log('  '.repeat(depth) + node.name);
});

// ❌ 비효율적인 재귀 (O(2^n))
const fibRecursive = (n) => {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
};

// ✅ 메모이제이션 (O(n))
const fibMemo = (() => {
  const cache = {};
  return function(n) {
    if (n in cache) return cache[n];
    if (n <= 1) return n;
    return cache[n] = fibMemo(n - 1) + fibMemo(n - 2);
  };
})();

// ✅ Tabulation (O(n), 공간 O(1))
const fibOptimal = (n) => {
  if (n <= 1) return n;
  let prev = 0, curr = 1;

  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }

  return curr;
};

// Git diff 유사 기능
const longestCommonSubsequence = (text1, text2) => {
  const m = text1.length;
  const n = text2.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
};

// 텍스트 유사도 계산
const textSimilarity = (text1, text2) => {
  const lcsLength = longestCommonSubsequence(text1, text2);
  const maxLength = Math.max(text1.length, text2.length);
  return (lcsLength / maxLength) * 100;
};

console.log(textSimilarity('ABCDGH', 'AEDFHR')); // 약 50% 유사

// 중복 파일 감지
const rabinKarp = (text, pattern) => {
  const d = 256; // 문자 집합 크기
  const q = 101; // 소수
  const m = pattern.length;
  const n = text.length;
  let patternHash = 0;
  let textHash = 0;
  let h = 1;
  const matches = [];

  // h = d^(m-1) % q
  for (let i = 0; i < m - 1; i++) {
    h = (h * d) % q;
  }

  // 패턴과 텍스트 첫 윈도우의 해시 계산
  for (let i = 0; i < m; i++) {
    patternHash = (d * patternHash + pattern.charCodeAt(i)) % q;
    textHash = (d * textHash + text.charCodeAt(i)) % q;
  }

  // 슬라이딩 윈도우
  for (let i = 0; i <= n - m; i++) {
    if (patternHash === textHash) {
      // 해시가 같으면 실제 문자열 비교
      if (text.substring(i, i + m) === pattern) {
        matches.push(i);
      }
    }

    if (i < n - m) {
      textHash = (d * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
      if (textHash < 0) textHash += q;
    }
  }

  return matches;
};

// 1단계: 문제 이해 및 예시 작성
// 입력: [3, 1, 4, 1, 5, 9, 2, 6]
// 출력: [1, 1, 2, 3, 4, 5, 6, 9]

// 2단계: 시간/공간 복잡도 목표 설정
// 목표: O(n log n) 시간, O(1) 공간

// 3단계: 알고리즘 선택
// 퀵소트 선택 (평균 O(n log n), 제자리 정렬)

// 4단계: 구현
const solve = (arr) => {
  return quickSort(arr);
};

// 5단계: 테스트 및 최적화
console.log(solve([3, 1, 4, 1, 5, 9, 2, 6]));