#2 Dictionaries-hash map

1) Ransom note

주어진 문자열 2개에서, 첫번째 s1에 주어진 문자들로 s2의 문자를 만들 수 있는지 체크하는 문제

s1 = give me one grand today night

s2 = give one grand today

 

s1에서 주어진 단어의 집합은 {give, me, one, grand, today, night}이고 이 단어들로 s2를 구성할 수 있으므로 Yes를 return, 아니면 No를 출력한다.

 

간단한 hash map 문제이다.

 

2) Two Strings

두 string s1,s2간의 sub string이 존재하는지를 묻는 문제이다.

알파벳 하나도 substring이므로 그냥 alphabet counting을 해서 같은게 하나라도 존재하면 OK, 아니면 NOK

 

3) Sherlock and Anagrams

string내에서 anagaram의 subset을 구하는 문제이다.

s내에서 string subset을 만들고, subset끼리 sub string을 체크하면서 counting하면 된다.

 

4) Frequency Queries

query list가 주어진다. 1은 insert, 2는 delete, 3은 해당 쿼리 숫자만큼 나타나는 number를 출력한다.

여기서 3 query결과들을 쭉 출력하면 된다.

각 쿼리마다 동작을 정의한다.

#1 Insert는 frequency check를 위해 map을 만들어서 빈도를 체크한다. 숫자가 작으면 배열로 해도 상관없으나 숫자가 10의 9승까지 가므로, 맵으로 구성한다.

 

즉 operation (1,1)을 수행하고나면 맵에는 Key : 1 , value : 1의 원소가 존재한다.

 

#2 Delete는 frequency에서 빼준다.

 

단, Operation3을 위해서 부가적인 map이 필요하다.

Operation 3쿼리값의 "빈도"를 가진 숫자가 몇개가 있냐? 를 counting도 해아한다.

그래서 frequency map을 만든다. 해당 빈도가 얼마나 자주 나타나는가를 체크하는것이다.

 

이것을 위해서 1과 2의 operation을 좀 수정해야한다.

예를들어, 숫자가 나타나는 빈도를 체크하는 map을 mp라고 하고, 빈도수의 빈도를 체크하는 맵을 freq라 한다.

첫번째 쿼리 이후 각 맵의 상태는

mp - <1,1>

freq - <1,1>

 

만약 여기서 insert 1이 한번 더 수행된다면

mp - <1,2>

freq - <1,0>, <2,1> 

 

이 되어야 한다.

 

즉, insert와 delete과정에서 그 숫자가 가지고 있던 이전 빈도값을 갱신해줘야 한다는 의미다.

Insert1이 두번째 수행되는 과정에서, mp에서 1의 빈도수를 올려주고(예제에서는 2가 되겟다), freq[2]++

단, 이전 빈도수값인 1은 빼줘야한다. freq[1]--;

delete 과정도 똑같다. mp에서 빼주되, freq의 값도 같이 체크해야한다.

그래야 operation 3에서 그 빈도수만큼 나오는 숫자가 몇갠지 체크할 수 있다.

 

5) Count Triplets

숫자 array에서 특정 배율을 만족하는 triplets개수를 찾는 문제. 개인적으로는 compact하게 짜는 idea가 안떠올랐다.

그래서 참고한 discussion에서는 아래와 같은 방법을 썼다.

 

map을 2개를 쓴다. mp1, mp2라고 하면

for문을 돌면서 처음 value부터 value * r의 값을 mp1에 넣는다. 즉 mp1은 candidate라고 할 수 있겠다.

만약 배율이 3이고, arr = {1,3,9,9,27,81} array에서 처음 value는 1이므로 다음 3이 나와야 triplets을 구성할 수 있다.

그래서 후보자에 넣어놓고, 다음 인덱스로 넘어갔을때 3이 나온다면 이제 3은 candidates에 있었으므로

이 3이 나타난 빈도수를 mp2로 넣는다. 위 예제에서는 mp2[9] = 1이 되겠다.

그럼 9로 넘어가게 되면 9는 1,3 각각의 빈도수를 carry받은 격이 된다. 그래서 그냥 이땐 result값을 mp2[9]의 값으로 삼으면 된다.

 

예를들어, arr가 {1,1,3,3,9} 라면

첫번째 루프에서 mp1[3] = 1, 두번째루프에서 mp[3] = 2

세번째 루프에서 mp2[9] = 2, 네번째 루프에서 mp[9] = 4

마지막 루프에서 4.

 

지속적으로 배수들이 계속 자기 개수를 윗자리쪽으로 carry하는 느낌이라고 보면 될것같다.

 

도대체 이런건 어떻게 생각하는걸까;;...