14. 가장 긴 공통 접두사

이 문제는 주어진 문자열 배열에서 가장 긴 공통 접두사를 찾는 것입니다. 접두사란 문자열의 시작 부분에서 공통으로 나타나는 부분 문자열을 의미합니다. 예를 들어, "flower", "flow", "flight"라는 세 문자열이 주어졌을 때, "fl"이 가장 긴 공통 접두사가 됩니다.

이제 주어진 해결 코드에 대해 단계별로 설명해 보겠습니다.

1. 알고리즘의 핵심 아이디어

이 알고리즘의 핵심은 첫 번째 문자열을 기준으로 삼고, 나머지 문자열들과 비교하면서 공통 접두사를 점차 줄여나가는 것입니다. 모든 문자열에 대해 공통으로 존재하는 접두사가 더 이상 없을 때까지 비교를 계속합니다.

2. 코드의 주요 로직 설명

• 초기 설정: 첫 번째 문자열을 기준으로 초기 접두사를 설정합니다.
• 반복 비교: 배열의 두 번째 문자열부터 마지막 문자열까지 순차적으로 비교합니다.
• 접두사 축소: 현재 접두사가 비교하는 문자열의 시작 부분과 일치하지 않으면 접두사를 한 글자씩 줄여가며 일치 여부를 확인합니다.
• 종료 조건: 접두사가 빈 문자열이 되면 더 이상 공통 접두사가 없다는 의미이므로 빈 문자열을 반환합니다.

3. 각 단계별 동작 과정

1. 초기화: pref는 첫 번째 문자열로 초기화됩니다. prefLen은 그 문자열의 길이를 나타냅니다.

   let pref = strs[0];
   let prefLen = pref.length;
   

2. 반복문: 두 번째 문자열부터 마지막 문자열까지 순회합니다.

   for (let i = 1; i < strs.length; i++) {
       let s = strs[i];
       ...
   }
   

3. 접두사 비교 및 축소: 현재 접두사 pref가 현재 문자열 s의 시작 부분과 일치하는지 확인합니다. 일치하지 않으면 접두사를 한 글자씩 줄여가며 일치 여부를 다시 확인합니다.

   while (pref !== s.substring(0, prefLen)) {
       prefLen--;
       if (prefLen === 0) {
           return "";
       }
       pref = pref.substring(0, prefLen);
   }
   

4. 결과 반환: 모든 문자열에 대해 공통 접두사를 찾은 후, 최종 접두사를 반환합니다.

   return pref;
   

4. 핵심 변수들의 역할

• pref: 현재까지 발견된 가장 긴 공통 접두사를 저장합니다.
• prefLen: 현재 접두사의 길이를 나타내며, 문자열 비교 시 사용됩니다.
• s: 현재 비교 중인 문자열입니다.

5. 왜 이 방법이 효과적인지

이 방법은 첫 번째 문자열을 기준으로 설정한 후, 다른 문자열들과 비교하면서 접두사를 점차 줄여나가는 방식으로 효율적으로 공통 접두사를 찾습니다. 각 문자열을 한 번씩만 순회하면서 접두사를 비교하므로 시간 복잡도는 O(S)이며, 여기서 S는 모든 문자열의 길이 합입니다. 따라서, 이 방법은 매우 효율적입니다. 또한, 접두사가 일치하지 않으면 즉시 줄여나가기 때문에 불필요한 비교를 최소화합니다.