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

	def sherlockAndAnagrams(s):
	dic = dict()
	for length in range(1, len(s)):
	for start in range(len(s)-length+1):
	ordStr = ''.join(sorted(s[start:start+length]))
	if ordStr in dic:
	dic[ordStr] += 1
	else:
	dic[ordStr] = 1
	count = 0
	for v in dic.values():
	count += v*(v-1)//2
	return count

view raw sherlockAndAnagrams.py hosted with ❤ by GitHub

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를 별도로 운영하면서 비교하면 해결된다. 자세한 설명은 코드로.

	def countTriplets(arr, r):
	rDic = dict()
	lDic = dict()
	for n in arr:
	if n in rDic:
	rDic[n] += 1
	else:
	rDic[n] = 1
	count = 0
	for n in arr:
	rDic[n] -= 1
	if n%r == 0:
	if n//r in lDic and n*r in rDic:
	count += lDic[n//r] * rDic[n*r]
	if n in lDic:
	lDic[n] += 1
	else:
	lDic[n] = 1
	return count

view raw countTriplets.py hosted with ❤ by GitHub

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

	def solve(queries):
	dic = dict()
	countDic = defaultdict(int)
	result = []
	for q in queries:
	if q[0] == 1:
	if q[1] in dic:
	countDic[dic[q[1]]] -= 1
	dic[q[1]] += 1
	countDic[dic[q[1]]] += 1
	else:
	dic[q[1]] = 1
	countDic[1] += 1
	elif q[0] == 2:
	if q[1] in dic:
	countDic[dic[q[1]]] -= 1
	dic[q[1]] = max(dic[q[1]]-1, 0)
	countDic[dic[q[1]]] += 1
	else:
	if q[1] in countDic and countDic[q[1]] > 0:
	result.append(1)
	else:
	result.append(0)
	return result

view raw frequencyQueries.py hosted with ❤ by GitHub