mjk study log

문제https://www.hackerrank.com/challenges/ctci-merge-sort/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=sorting Merge Sort: Counting Inversions | HackerRankHow many shifts will it take to Merge Sort an array?www.hackerrank.com 풀이minimum swaps 2 와 비슷한 문제라 비슷한 방식으로 풀면 되겠지 라고 생각했지만,minimum swaps 2에서는 숫자가 한번씩 반복되며, 착하게 1에서부터 n 까지 나온다.하지만 이 ..

문제https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=sorting Fraudulent Activity Notifications | HackerRankPrint the number of times a customer receives a notificationwww.hackerrank.com 풀이median 을 구하는 방법을 파악하는게 이 문제의 메인이다. 처음(코드1)에는 d개의 숫자를 sort해서 가운데의 2개의 숫자의 합이나 1개의 ..

문제https://www.hackerrank.com/challenges/frequency-queries/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps Frequency Queries | HackerRankProcess the insert/delete queries and report if any integer is there with a particular frequency.www.hackerrank.com 풀이원래는 int freq[10^9+1] = {0} 를 사용해 x,y,z가 나오는데로 frequency를 updat..

문제https://www.hackerrank.com/challenges/count-triplets-1/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps Count Triplets | HackerRankReturn the count of triplets that form a geometric progression.www.hackerrank.com 풀이 hashmap을 사용하지 않으면 time limit exceed 가 뜬다.이 문제에서는 총 2개의 hash map을 사용하는데, triplet이 (first, second, th..

문제https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps Sherlock and Anagrams | HackerRankFind the number of unordered anagramic pairs of substrings of a string.www.hackerrank.com 풀이array 안의 모든 anagram의 pair 의 수를 구하는 문제이다.여기서 중요한 포인트는 #pair = (count * (count-1))..

문제https://www.hackerrank.com/challenges/crush/problem?h_l=interview&isFullScreen=true&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays Array Manipulation | HackerRankPerform m operations on an array and print the maximum of the values.www.hackerrank.com 풀이각각의 query 마다 array를 업데이트하는 방법은 O(queries_rows * n) 이 걸려 n이 커질수록 너무 오래걸리게 된다.이 문제는 prefix sum을 사용한 문제로 우리가 필요한 것만 upd..

문제: https://www.hackerrank.com/challenges/minimum-swaps-2/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays Minimum Swaps 2 | HackerRankReturn the minimum number of swaps to sort the given array.www.hackerrank.com 풀이:minimum swap (최적의 바꾸기)를 구하려면 cycle을 파악해야한다.여기서 cycle이란 index_before -> index_after가 계속 연결된 체인을 말한다. 예를 들어, arr = [4,..