HackerRank11 Max Array Sum def maxSubsetSum(arr): if len(arr) == 1: return arr[0] dp = [arr[0], max(arr[:2])] + [0]*(len(arr)-2) for i in range(2, len(arr)): dp[i] = max(arr[i], dp[i-1], dp[i-2]+arr[i]) return dp[-1] 인접하지 않은 부분집합의 합 중 제일 큰 합을 출력하는 문제였다. 먼저 시간 복잡도를 생각하지 않고 구현하면, 1) 모든 부분집합을 구하고 2) 부분집합 중 인접하지 않게 필터링하고 3) 남은 부분집합 중의 합을 구한다. 물론 시간 복잡도가 넘어간다. 다이나믹 프로그래밍을 이용해서 풀어보자. Dynamic programming은 Divide and conquer와 혼동할.. 2019. 9. 6. Triple sum def triplets(a, b, c): a = list(set(a)) b = list(set(b)) c = list(set(c)) count = 0 a.sort() b.sort() c.sort() frontIdx = 0 backIdx = 0 for ct in b: while frontIdx < len(a) and a[frontIdx] 2019. 5. 12. Greedy Florist def getMinimumCost(k, c): total = 0 counter = 0 length = len(c) c.sort(reverse=True) for i in range(0, length): total += (counter + 1) * c[i] if length != k and (i + 1) % k == 0: counter += 1 return total 탐욕 알고리즘 문제는 복잡한 문제는 안나온다. 항상 제일 높은, 비싼 비용을 먼저 선택하는 방식으로 구현하기 때문이다. 이 문제는 로직은 잘 만들었는데 반복문을 돌 때 역순, i의 초기값을 길이-1로 시작했다가 계속 테스트 케이스를 통과를 못해서 오류를 찾는데 한참이나 걸렸다. 간단하게 k 값이 2이고 길이가 10이면, 2명이 지나고 나서 카운.. 2019. 5. 12. Special Palindrome Again def substrCount(n, s): l = [] count = 0 cur = None # 각 문자의 개수를 카운팅해서 리스트에 추가, 연속되는 문자처리 for i in range(n): if s[i] == cur: count += 1 else: if cur is not None: l.append((cur, count)) cur = s[i] count = 1 # 마지막 문자 카운팅 처리 l.append((cur, count)) ans = 0 # 모두 같은 회문 찾기 # 단일 회문을 포함한 모든 경우의 회문 개수 구하는 것 for i in l: ans += (i[1] * (i[1] + 1)) // 2 # 가운데 대칭 회문 찾기 for i in range(1, len(l) - 1): if l[i - 1].. 2019. 5. 12. Sherlock and the Valid String def isValid(s): isValid = 'YES' # 정렬해서 개수 카운팅 쉽게 변환 sortedStr = ''.join(sorted(s)) firstLetter = sortedStr[0] cmpCount = 1 # 기준이 되는 카운팅 개수 구하기 for c in sortedStr[1:]: if c == firstLetter: cmpCount += 1 else: firstLetter = c break counter = 1 limit = 0 # 기준 카운팅 개수와 현재 카운팅 개수가 2번 다를 경우 유효하지 않음 for c in sortedStr[cmpCount+1:]: if c == firstLetter: counter += 1 else: if cmpCount != c.. 2019. 5. 11. 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. 이전 1 2 다음
