HackerRank Interview Preparation Kit > Dictionaries and Hashmaps

HackerRank의 Interview Preparation Kit > Dictionaries and Hashmaps의 Medium 이상 문제

Sherlock and Anagrams - medium

문제요약

문자열 s가 주어지면 s의 substring들의 anagram pair의 수를 계산 (2<=|s|<=100)

Sample Input

2

abba

abcd

Sample output

4

0

풀이

각 substring을 정렬 후 나타나는 개수를 카운팅. 동일 문자들을 사용한 substring이 n개면, 이 중 2개를 선택하는 경우의 수 만큼의 pair가 존재. n*(n-1)/2

Count Triplets - medium

문제요약

n개의 integer배열 arr과 등비 r이 주어지면, (i,j,k) i<j,k인 등비수열의 수를 계산

(1<=n<=10^5, 1<=r<=10^9, 1<=arr[i]<=10^9)

Sample Input

4 2

1 2 2 4

Sample output

2

풀이

가능한 수를 전부 계산하다가, 도통 모르겠어서 답을 보고 이해하는데도 오래걸리...

(a, ar, arr)대신 (a/r, a, a*r)로 접근을 변경하면 r을 한 번만 곱하거나 나누는 것으로 판단할 수 있다.

arr의 각 수의 count를 계산해서 dictionary에 저장, arr을 각 항목 a마다 a/r과 a*r의 수를 곱해주면 (a/r, a, a*r)  각 a마다 경우의 수가 계산된다.

r = 1인 경우는 a/r, a, a*r이 모두 같기 때문에, 고려할 필요가 있고 a/r과 a*r의 수를  찾을 dictionary를 별도로 운영하면서 비교하면 해결된다. 자세한 설명은 코드로.

Frequency queries - medium

문제요약

q개의 query가 주어졌을 때, 값에 따라 수행 후 최종 결과 반환

(1<=q<=10^6, 1<=x,y,z<=10^9, q[i][0] ∈ {1,2,3} ,1<=q[i][1]<=10^9)

[1 x] : x 추가

[2 y] : y 하나 제거

[3 z] : z개만큼 있는 수가 있으면 1, 없으면 0

Sample Input

8

1 5

1 6

3 2

1 10

1 10

1 6

2 5

3 2

Sample output

0

1

풀이

해당 수를 추가하고 제거한 후 개수를 판단하기 때문에, query에 따라 개수를 저장하고 3이 나오면 개수에 맞는 수가 있는지를 판단한다. 개수를 dictionary에 {수:개수}로 저장하여 판단했으나, timeout.

{개수:개수에 해당하는 수의 개수} dictionary를 추가로 저장하고 개수의 수가 있는지 판단하는 부분도 O(1)으로 변경