분류 전체보기91 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. Merge Sort: Counting Inversions def merge(counter, sourceArr, tempArr, start, mid, end): leftIndex = start rightIndex = mid + 1 targetIndex = start for i in range(start, end+1): tempArr[i] = sourceArr[i] while leftIndex 2019. 5. 11. 이전 1 2 3 4 5 6 7 8 ··· 16 다음
