본문 바로가기

Map3

Frequency Queries def freqQuery(queries): respond = [] dic = {} countDic = collections.defaultdict(list) for query in queries: qtype = query[0] value = query[1] if qtype == 1: if value in dic: prev = dic[value] dic[value] += 1 countDic[prev].remove(value) countDic[dic[value]].append(value) else: dic[value] = 1 countDic[1].append(value) elif qtype == 2: if value in dic: if dic[value] == 0: continue prev = dic[valu.. 2019. 5. 11.
Minimum Swaps def minimumSwaps(arr, n): findIndex = 1 swapCount = 0 hashNumber = dict((val, idx) for idx, val in enumerate(arr)) for i in range(0, n): if arr[i] == i+1: continue else: foundIndex = hashNumber[i+1] hashNumber[i+1], hashNumber[arr[i]] = i, foundIndex arr[i], arr[foundIndex] = arr[foundIndex], arr[i] swapCount += 1 return swapCount 간단히 문제를 풀면 이중 포문 을 돌면서 자신의 위치에 맞는 값을 찾아서 교환하고 카운팅을 올려주면 된다. 대략 n .. 2019. 4. 28.
Count Triplets def countTriplets(arr, r): m2 = defaultdict(int) m3 = defaultdict(int) total = 0 for val in arr: if val in m3: total += m3[val] # 1 2 2 4 if val in m2: m3[val * r] += m2[val] m2[val * r] += 1 return total 이 문제를 처음 풀었을 때는 삼중 포문을 사용 했었다. 첫번째 값을 기준으로 두번째, 세번째 값을 찾는 방식이었는데 세 숫자의 인덱스가 a < b < c 순이 되는지 확인했다. 그 상태에서 두번째, 세번째 숫자를 찾는 방법을 아무리 최적화 하려고 해도 방법이 안떠오르는 것이다. 그래서 첫번째 값을 기준으로 하는게 아니라 가운데 값을 기준으로 하.. 2019. 4. 28.