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)으로 변경