hackerrank4 Fraudulent Activity Notifications def get_median(counter, d): count = 0 for i, c in enumerate(counter): count += c if count > d // 2: # 여기서 찾은 i 값이 중앙값(d=홀수 일 경우) break if d % 2 == 1: return i * 2 else: for j in range(i, -1, -1): # 전 인덱스부터 검사하는게 아니라 현재 인덱스부터 검사한다. # 카운팅 한 개수이기 때문에 같은 수 일 수 있다. count -= counter[j] if count < d//2: break return i + j def activityNotifications(expenditure, d): count = 0 counter = [0]*201 for exp in.. 2019. 4. 29. Array Manipulation def arrayManipulation(n, queries): newArr = [0] * n for start, end, value in queries: newArr[start-1] += value if end < n: newArr[end] -= value total = 0 maxVal = 0 for v in newArr: total += v maxVal = max(maxVal, total) return maxVal 문제를 보는 순간 아이디어나 패턴이 떠오르면 바로 해당 방식으로 접근하지만, 대부분의 경우에는 그렇지 않기 때문에 거친 방식 으로 접근한다. 거친 방식이란? 시간 복잡도를 생각하지 않고 문제를 푸는 방식이다. Time out 을 신경쓰지 않는 해결 방안 그래서, 쿼리 만큼 반복문을 돌면서 시.. 2019. 4. 28. 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. 이전 1 다음
