ransom-note.md

Ransome Note

문제:

Given a magazine of words and a ransom note, determine if it’s possible to “cut out” and create the ransom note from the magazine words.

문제 해설:

랜섬노트란, 잡지나 신문의 글자를 오려서 만든 글을 뜻한다.

위의 문제는 주어진 매거진이라는 문자열을 단어별로 오려서(잘라내서) 주어진 문자열(str)을 만들 수 있는지에 대한 여부를 리턴하시오

WIL(What I Learned this problem)

이 문제를 통해서 알게 된 사실들에 대해 간단하게 정리한다.

Solution 1

• 접근

  매거진과 만들 문자열을 직접 비교하여서 해결할 수 있다. 구체적으로는 문자열과 매거진을 split(' ') 하여서 배열 상태에서 구현하였다. 문자열이 매거진에 존재한다면 해당 문자열을 매거진배열에서 제거하는 방식으로 해결하였다. 해당 문자열을 제거하는 이유는 중복되는 단어를 비교하기 쉽게 하기 위해서이다.

• 문제점

  시간복잡도가 O( n² ) 이다. 이는 찾고자 하는 수가 많아지면 분명히 시간초과오류에 빠지게 된다. 즉 효율적이지 않은 알고리즘 방법이다. 분명한 개선점이다.

  원본의 배열을 변형시킬 수 밖에 없다. 매거진 배열에서 해당 문자열을 찾으면 제거해줘야하는데, 이 상태에서 제거를 하게 되면 원본 배열이 동적으로 변형될 수 밖에 없는 구조다. 여기서는 이 배열을 한 곳에서만 사용하기 때문에 원배열의 변형으로 인한 side effect가 발생할 확률이 없다. 하지만 이것이 실제적으로 여러 군데에서 사용하는 함수라면 원본배열의 변화는 어디서든 문제를 야기할 수 있다.

  관련키워드) mutable vs immutable

Solution 2

• 접근

  객체를 사용하는 방법이다. 매거진의 단어들을 key로 하고, 각각의 단어의 수를 value로서 객체를 만든다. 이 과정이 비싼 작업일 수 있지만, 이 과정을 거치면 문자열과 매거진을 비교하는 것의 복잡도(O(1))가 현저하게 줄어드는 장점이 있다.

Hash Table

Solution 2 와 연결

해쉬 테이블은 key-value를 쌍으로 갖는 자료구조이다. 자바스크립트의 객체는 해쉬테이블의 한 종류이다.

해쉬테이블이라고 해서 뭔가 다른 특이한 것이라고 생각했었는데, 자주 사용하는 객체가 바로 해쉬테이블의 일종이였다니... 부족하도다!! 🤯

해쉬테이블은 키를 해쉬함수 통해서 나온 새로운 키를 갖도록 하여 값을 할당한다. 해쉬함수를 어떻게 만드냐에 따라서 균등한 구조가 되느냐 한쪽으로 치우친 구조가 되드냐를 판가름한다.

해쉬테이블의 탐색,추가,삭제,수정(CRUD)는 모두 시간복잡도가 O(1)이기때문에 굉장히 효율적이다. 하지만 해쉬충돌을 항상 염두에 두어야한다. 위에서 말했듯이 어떤 해쉬함수인지에 따라서 구조의 효율성, 안정성이 결정된다. 그럼에도 충돌은 언제나 야기하기 때문에 이를 보완하는 방법을 항상 생각해야한다. 이때문에 해쉬테이블의 충돌을 극복하는 여러가지 방법들이 존재한다.

관련키워드

• 개방주소법 : 선형탐사법, 제곱탐사법, 이중 해싱
• 분리연결법