게시됨

문자와 관련된 일반적인 과제 극복: 타입스크립트의 이야기

작성자

GitHub 저장소: https://github.com/ImBIOS/common-char-extractor-ts

코딩 면접에서 알고리즘 문제는 단순히 기술 지식을 평가하는 것 이상으로, 지원자의 문제 해결 능력을 보여주는 창문과 같습니다. 개발자의 필수적인 기술인 문자열 조작과 관련된 흥미로운 문제가 자주 등장합니다. 오늘은 여러 문자열에서 공통된 문자를 찾는 매력적인 문제와 TypeScript를 사용하여 이 문제를 해결한 방법을 살펴보겠습니다.

펼쳐진 과제

주어진 과제는 겉보기에는 간단하지만 속임수가 있는 복잡한 문제였습니다. 문자열 배열이 주어지면 각 문자열에서 같은 위치에 있는 문자를 추출하여 배열로 반환하는 함수를 작성해야 했습니다. 예를 들어, ["abcd", "bcd", "cde", "cdef"]라는 입력이 주어지면, 예상되는 출력은 ["c", "d"]가 됩니다. 이는 'c'와 'd'가 모든 문자열에서 같은 위치에 있는 공통 문자인 것을 의미합니다.

솔루션 제작

우리는 솔루션에 TypeScript를 선택했으며, 이는 TypeScript의 강력한 타입 시스템이 코드의 신뢰성과 개발자 생산성을 향상시키기 때문입니다. 첫 번째 단계는 첫 번째 문자열의 각 문자를 반복하고, 이를 참조하여 이후 문자열의 해당 문자와 비교하는 것이었습니다.

/**
 * 입력 배열 내 모든 문자열에서 같은 위치에 있는 문자를 추출하여 배열로 반환합니다.
 *
 * @param {string[]} words - 분석할 문자열 배열.
 * @returns {string[]} 제공된 모든 문자열에서 공통으로 나타나는 문자 배열. 첫 번째 문자열에 있는 문자 순서를 유지합니다.
 */
export function extractCommonLetters(words: string[]): string[] {
  if (words.length === 0) {
    return []
  }

  const copiedWords = [...words]
  const result: string[] = []
  const referenceWord = copiedWords[0]

  // 첫 번째 단어의 각 문자를 반복합니다.
  for (let i = 0; i < referenceWord.length; i++) {
    const currentChar = referenceWord[i]
    let isCharCommonAcrossWords = true

    // 현재 문자가 다른 모든 단어에 있는지 확인합니다.
    for (let j = 1; j < copiedWords.length; j++) {
      const word = copiedWords[j]
      const charIndex = word.indexOf(currentChar)

      // 문자가 발견되지 않으면 반복을 중단하고 플래그를 false로 설정합니다.
      if (charIndex === -1) {
        isCharCommonAcrossWords = false
        break
      } else {
        // 중복을 처리하기 위해 찾은 문자를 단어에서 제거합니다.
        copiedWords[j] = word.slice(0, charIndex) + word.slice(charIndex + 1)
      }
    }

    // 문자가 모든 단어에 공통으로 나타나면 결과에 추가합니다.
    if (isCharCommonAcrossWords) {
      result.push(currentChar)
    }
  }

  return result
}

이 스니펫은 우리 접근 방식의 핵심을 담고 있으며, 문제를 해결하기 위한 가독성과 간결한 논리를 강조합니다.

더 나아가기: 솔루션 테스트

솔루션을 검증하기 위해, 우리는 기본적인 사례부터 특수 문자와 대소문자 구분을 포함하는 더 복잡한 사례까지 다양한 시나리오를 다루는 테스트 사례 모음을 사용했습니다. 이러한 철저한 테스트는 광범위한 입력에 걸쳐 알고리즘의 견고성과 정확성을 보장했습니다.

공간 및 시간 복잡도 분석

반성해 보면, 솔루션의 시간 복잡도는 주로 첫 번째 문자열에 있는 문자 수(이를 N으로 표시하겠습니다)와 문자열의 총 수(이를 M으로 표시하겠습니다)에 의해 결정됩니다. 첫 번째 문자열의 각 문자에 대해 다른 모든 문자열에서 해당 위치에 있는지 여부를 확인하므로 시간 복잡도는 O(N*M)이 됩니다.

솔루션의 공간 복잡도는 O(N)이며, 이는 공통 문자를 배열에 저장하기 때문입니다. 모든 문자가 모든 문자열에서 공통으로 나타나는 최악의 경우, 이 배열의 크기는 첫 번째 문자열의 길이에 비례합니다.

개선 방향

솔루션은 적당한 수의 문자열과 문자에 대해 효율적이지만, 항상 개선의 여지가 있습니다. 성능을 더욱 향상시키기 위한 몇 가지 전략은 다음과 같습니다.

  1. 조기 종료: 어떤 시점에서 문자가 모든 문자열에서 해당 위치에 일치하지 않으면 반복을 조기에 중단하여 불필요한 비교를 줄일 수 있습니다.

  2. 짧은 문자열 최적화: 가장 짧은 문자열을 참조로 사용하면 확인해야 하는 최대 문자 수가 줄어들기 때문에 반복 횟수를 줄일 수 있습니다.

  3. 병렬 처리: 대규모 데이터 세트의 경우 문자열 간에 문자를 동시에 비교하는 병렬 처리 기술을 활용하면 실행 시간을 크게 줄일 수 있습니다.

  4. 해싱 기술: 해싱 맵을 사용하여 문자 위치와 발생 횟수를 추적하면, 특히 광범위한 문자열 집합을 처리할 때 공통 문자를 식별하는 더 정교한 방법을 제공할 수 있습니다.

마무리

공통 문자 문제는 문자열 조작 문제의 우아함을 보여주는 놀라운 증거이며, 개발자는 알고리즘과 데이터 구조의 뉘앙스를 탐구하도록 초대합니다. TypeScript를 통해 우리는 솔루션을 찾았을 뿐만 아니라 명확성, 타입 안전성 및 효율적인 문제 해결의 여정을 받아들였습니다.

마무리하며, 코딩 과제를 통한 여정은 목적지에 도달하는 것만큼이나 택한 경로에 대한 것이라는 것을 기억하는 것이 중요합니다. 이 문제를 포함하여 각 문제는 기술을 연마하고, 접근 방식을 재고하고, 가장 중요한 것은 계속 배우는 독특한 기회를 제공합니다.

트위터에서 논의하기

공유