[js] 글자 지우기

문자열 my_string과 정수 배열 indices가 주어질 때, my_string에서 indices의 원소에 해당하는 인덱스의 글자를 지우고 이어 붙인 문자열을 return 하는 solution 함수를 작성해 주세요.

제한사항

• 1 ≤ indices의 길이 < my_string의 길이 ≤ 100
• my_string은 영소문자로만 이루어져 있습니다
• 0 ≤ indices의 원소 < my_string의 길이
• indices의 원소는 모두 서로 다릅니다.

나의 풀이

function solution(my_string, indices) {
    let idx = indices.sort((a, b) => b - a);
    let string = [...my_string];
    
    for (let i=0; i<idx.length; i++) {
        string.splice(idx[i], 1);
    }
    
    return string.join('');
}

indices를 건드리지 않으면... 자꾸 인덱스가 어긋나서 한참 고민하다...

• indices를 내림차순으로 정렬한다! 이렇게 해서 인덱스가 어긋나는 문제를 해결했다.
• 조작이 쉽도록 my_string을 배열로 변환한다.
• 배열 메서드를 써보려고 노력했으나 안되겠어서 그냥 idx를 순환하는 for 문을 돌렸다.
  - splice() 메서드를 사용해 string에서 idx의 i번째 인덱스를 1개씩 삭제한다.
• for문이 끝난 후 string을 join('')을 사용해 문자열로 합쳐서 리턴한다.

다른 풀이 1

const solution=(s,d)=>[...s].filter((v,i)=>!d.includes(i)).join('')

• 주어진 문자 s를 배열로 변환한다.
• filter() 메서드를 사용한다.
  • 각 문자와 그 인덱스를 순회하면서 d 배열에 해당 인덱스가 포함되지 않은 문자들만 필터링한다. (!d.includes(i))
• join('')을 통해 다시 하나의 문자열로 합친다.

아...! filter 메서드를 사용하고 싶었는데 include()를 사용해야 했던 거구나...! 이렇게 하고 싶었던 거였어 ㅠㅠ

다른 풀이 2

function solution(my_string, indices) {
  const set = new Set(indices);
  return [...my_string].filter((_, i) => !set.has(i)).join('');
}

• indices 배열을 Set으로 변환하여 검색 속도를 최적화한다.
• my_string을 배열로 변환하여 각 문자를 순회한다.
• filter() 메서드를 사용하여 인덱스가 Set에 포함되지 않은 문자들만 필터링한다.
• 필터링된 문자들을 join('') 메서드를 사용하여 다시 문자열로 합친다.

어?! 여긴 Set을 쓰네?! 나는 주로 중복 제거를 할 때만 Set을 사용했었기 때문에 여기서 왜 Set을 쓰는지 궁금했다.

Set → 검색 속도 최적화

• 배열의 검색 속도: 배열에서 특정 요소가 포함되어 있는지 확인하려면 includes() 메서드를 사용해야 한다. 이는 평균적으로 O(n)의 시간복잡도를 가진다. 따라서 배열의 길이가 길어질수록 검색 시간이 늘어난다.

• Set의 검색 속도: Set은 해시 테이블을 기반으로 하여 요소를 저장하고 검색하기 때문에, 특정 요소가 Set에 포함되어 있는지 확인하는 작업이 평균적으로 O(1) 시간복잡도를 가진다. 즉, 검색 속도가 매우 빠릅니다.

따라서 배열에서 include() 메서드를 사용해 특정 요소를 검색해야 할 일이 있을 땐 Set을 사용하는 것이 성능 면에서 더 좋다.