Archive

https://www.hackerrank.com/challenges/special-palindrome-again/problem Special String Again | HackerRank Find Special sub-strings in a string. www.hackerrank.com 풀이 입력으로 문자열 길이, string이 주어졌을 때, 다음 조건에 만족하는 substring 개수를 구하는 문제 substring에 포함된 모든 문자가 같은 경우. ex) aaa substring의 가운데 하나를 제외한 양 옆의 모든 문자가 같은 경우. ex) aadaa ex) s = mnonopoo special substrings = {m, n, o, n, o, p, o, o, non, ono, opo, oo} ..

https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem Sherlock and the Valid String | HackerRank Remove some characters from the string such that the new string's characters have the same frequency. www.hackerrank.com 풀이 입력으로 string이 주어지고, 각 문자의 빈도 수가 같거나, 하나의 문자를 제거했을 때 빈도 수가 같으면 valid string으로 정의. 먼저 입력 string에 대해 frequency를 세고, 해당 정보를 dictionary에 저장. 그리고 frequency에 대한 빈도 수를 ..

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칸 이전까지 계산된 최대 금액 비교 하지만 문제 조건..