잠깐!

해당 시리즈의 문제는 wecode codeCata, 또는 LeetCode의 문제입니다.

앞으로 wecode가 종료되어도 LeetCode의 문제를 통해 이어갈 예정이니, 참고해주세요.

또한 솔루션이 아니고, 제가 생각한 것을 로직으로 어떻게 그려냈는지 코드를 올리는 글입니다.

이에 알고리즘의 해답에 가까운 코드는 아닐 수 있습니다.

배열 내 같은 알파벳 단어 묶어주기

// 문자열 비교 함수 정의

function equal(str, str2){
  if(str === str2){
    return [str];
  }
  // 동일 문자열 그대로 반환
  
  let newStr = str.split(``);
  let newStr2 = str2.split(``);
  // 글자 단위로 나누기
  let count = 0;
  
  if(newStr.length !== newStr2.length){
      return ;
    }
  // 두 문자열의 길이가 다르면 종료
  
  for(let i = 0; i< newStr.length; i++){
    if(newStr2.includes(newStr[i])){
      count++
    }
  }
  // 길이가 다르고, 동일 문자열이 아닐 때, 앞 문자열의 글자를 포함하는지 체크
  // 포함 시 count 증가
  
  let result = [];
  if(count === newStr.length){
    result.push(str, str2);
  }
  // 만약 count와 앞 문자열의 글자수가 일치하면 배열 요소로 추가
  
  return result
}


const groupAnagrams = strs => {
  if(!strs) return;
  // 입력이 없으면 종료
  
  let arr = [];
  for(let i = 0; i< strs.length ; i++){
    // 입력의 길이만큼 반복
    let test = [];
    
    for(let j=0; j<strs.length; j++){
      // 2중 for문으로 배열 내 각 요소 [i]를 기준으로 전체를 검사
      let result = (equal(strs[i], strs[j]));
      // 반복문 내에서 정의한 eqaul 함수 실행(3중 for문 형태)
      
      if(result[0] !== undefined && result[1] !==undefined){
        test= [...test, result[0], result[1]]
        strs.splice(j, 1)
      }
      // result return은 두 문자열로 구성된 배열의 형태,
      // 알파벳이 겹치는 단어가 있을 때(!undefined)
      // test.concat(equal() =>{ return })
      // splice로 원본 배열 내에서 겹치는 단어를 제거하며 진행
      
      if(result[0] !== undefined && result[1] ===undefined){
        test = [...test, result[0]];
      }
      // 원본 배열 strs 마지막 요소에 대한 concat
      // splice 가 있기 때문에 겹치는 단어는 제거된 상태이므로 그냥 concat.
      
      if(j === strs.length -1){
        arr.push(Array.from(new Set(test)));
      }
      // 한 요소를 기준으로 전체 비교를 마치면 arr에 추가
      // 추가 형태는 Set의 배열형태 (중복 제거 - equal()은 중복되는 단어 또한 반환)
      // 기대하는 ouput이 2중 배열 형태이므로, concat이 아닌 Array.from 
    }
  }
  
  return arr // 2중 배열의 형태로 반환
};

좀 길긴 합니다.

아무래도 한시간동안 머리를 열심히 싸매고 있었던 것 같은데, 처음에는 3중 for문을 어떻게 구현해야 할까 하다가 그냥 문자열 비교 for문을 함수로 분리하는게 편하겠다고 생각했습니다.

1. input은 단일 배열구조인데, output은 2중 배열 구조를 요구했기에 for문을 2개 중첩시켜서 반환해야겠다는 생각을 했습니다.

2. 두 문자열의 글자 단위 비교는 하나의 for문을 요구하는데, 그렇다면 결국 2중 for문 내에서 하나의 for문을 더 추가해야 하기에 3중 for문의 형태를 떠올렸습니다.

3. 이에 문자열을 비교하는 하나의 for문을 함수로 분리, 위에서 정의하고

4. 2중 for문 중 비교를 실행해야 하는 위치에서 함수를 실행시킵니다.

5. 이에 3개의 for문이지만 비교적 로직을 구현하는 데 큰 어려움이 없는 형태의 코드가 완성됩니다.

결론

생각한다고 전부 정답은 아니겠다는 생각이 이제는 피부로 와닿습니다.

해당 구조의 문제를 해결할 때, 3개의 for 문을 돌릴 경우 시간복잡도는 O(n^3)으로, 이정도 수준의 알고리즘 문제에서 그정도의 복잡성을 가질 필요가 있는지 의심해야 했습니다.

그러나 머리는 3개의 for문을 중첩시키는 것 밖에 답이 없다는 생각을 하고 있었나봅니다.

만약, 문자열 비교를 사전에 실행하는 구조로 짤 수 있었다면 2중 for문 밖에 있으니 O(n^2)겠지만, 기준 요소로 전체 배열을 순회하는 형태의 로직이다보니 3개를 사용하게 된 것 같습니다.

어떤 방법이 보다 더 좋았을까 고민하게 되는 문제는 매번 그렇지만 이번 코드는 더욱 궁금하네요.

조금은 나아갔나 싶다가도 결과물은 처참하니 매번 정진해야겠다는 생각만 가득합니다.

그럼 이번 글은 여기서 마치겠습니다.