Archive

https://www.hackerrank.com/challenges/ctci-merge-sort/problem Merge Sort: Counting Inversions | HackerRank How many shifts will it take to Merge Sort an array? www.hackerrank.com 풀이 예제처럼 bubble sort로 구현하면 timeout 발생 merge sort로 구현해도 timeout 발생함 merge 부분에서 list의 append함수를 지역 변수로 사용하는게 빠름. 필요한 정보들( len(list) 등)을 미리 변수에 할당하고 사용하는게 빠름. 가운데 index를 계산해 둘 씩 나누다가, 합칠 때 inversion 경우를 count함. i < j 일 때, a..

https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem Fraudulent Activity Notifications | HackerRank Print the number of times a customer receives a notification www.hackerrank.com 풀이 d길이를 유지하면서 median을 유동적으로 계속 구해줘야함. 한 번 iteration할 때마다 sort하고, median을 직접 계산하면 timeout. 문제 조건에서 expenditure[i]는 0 이상 200 이하의 정수임을 명시했기 때문에 이를 count하는 배열을 만들어 median을 구하는데 활용. count[expendit..

https://www.hackerrank.com/challenges/count-triplets-1/problem Count Triplets | HackerRank Return the count of triplets that form a geometric progression. www.hackerrank.com 풀이 숫자로 구성된 배열, 등비급수 공비 r이 주어졌을 때, 세 개의 숫자의 index가 오름차순을 만족하는 배열의 수를 구하는 문제 단순히 숫자 종류만 count해서 곱하면 정답보다 많은 수를 계산하게되므로, index가 오름차순인 조건을 만족하는게 중요 단순반복으로 구현하면 timeout 발생. dictionary 자료구조를 사용해 현재 숫자에서 가능한 등비수열 개수를 count하는 dynami..

https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem Sherlock and Anagrams | HackerRank Find the number of unordered anagramic pairs of substrings of a string. www.hackerrank.com 풀이 문자열이 주어졌을 때 anagram의 개수를 구하는 문제 dictionary를 사용해 substring의 출현 빈도를 count함. key : substring, value : count def sherlockAndAnagrams(s): answer = 0 substr_dict = {} for window_size in range(1, len(s)): for..

https://programmers.co.kr/learn/courses/30/lessons/17685 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g � programmers.co.kr 풀이 Trie 자료구조를 활용 먼저 단어를 Trie에 넣음. 그리고 Trie에서 단어를 찾을 때 각 단어마다 입력해야 할 문자 수를 어떻게 찾을지 생각해야 함. 기본이 되는 Node를 만들 때, data, children 외에 below_word_counts를 추가해 해당 단어 밑에 단어가 몇 개가 남았는지 개수를 저장. 처음 insert할..

https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 �� programmers.co.kr 풀이 동적 계획법(dynamic programming) 문제 dp[i] : i번째 집까지 포함해 마을을 털었을 때의 최대 금액 dp[i] = max ( dp[i-2] + money[i] , dp[i-1]) 현재 집을 털때 획득 가능한 돈 + 2칸 이전 집까지 계산된 최대 금액 vs 현재 집을 털지 않고, 1칸 이전까지 계산된 최대 금액 비교 하지만 문제 조건..

https://www.hackerrank.com/challenges/new-year-chaos/forum Discussion on New Year Chaos Challenge Determine how many bribes took place to get a queue into its current state. www.hackerrank.com 풀이 Input : 1 이상의 정수로 구성된 list 순번이 뒤에 있는 사람이 바로 앞 사람에게 뇌물을 줌으로써 순서를 바꿀 수 있음. 한 사람이 사용할 수 있는 최대 뇌물은 2. -> 한 숫자마다 최대 2번 swapping 모든 경우의 수를 구하거나, 리스트 값을 덮어씌우거나 새로운 저장공간을 할당해 현황을 매번 저장할 필요 없음. 뇌물을 받은 개수만 counti..

https://www.hackerrank.com/challenges/maximum-subarray-sum/problem Maximum Subarray Sum | HackerRank Find the maximal value of any (subarray sum % m) in an array. www.hackerrank.com 풀이 Input : 숫자 배열 arr, 나눌 수 m subarray : arr[ i : j ] index i부터 j까지 연속된 배열 문제 : subarray의 수를 다 더하고, m으로 나누었을 때 나머지의 최댓값 구하기. 모든 경우의 수를 다 해보는 O(N^2) 은 당연히 timeout $P_{i}$ : 0 ~ i번째 index까지 수를 더한 뒤, m으로 나누었을 때의 나머지 $S_{..