Archive

https://www.hackerrank.com/challenges/candies/problem Candies | HackerRank Help Alice to save money by minimizing the total number of candies. www.hackerrank.com 풀이 2번 iteration을 사용. 오른쪽으로 iteration돌 때는 오름차순일 때 dp 값을 채워줌. 왼쪽으로 iteration돌 때는 내림차순일 때 dp값을 채워줌. def candies(n, arr): n = len(arr) # 최소값은 1로 문제에서 주어짐. dp = [1] * n for i in range(1, n): # 다음 원소가 더 크면 dp값을 증가해줌. if arr[i-1] < arr[i]: dp[..

https://www.hackerrank.com/challenges/abbr/problem Abbreviation | HackerRank Make two strings equal www.hackerrank.com 풀이 두 개의 문자열 a, b를 입력받음. 문자열 a를 다음 두 가지 방법을 사용해 문자열 b를 만들 수 있으면 "YES"를, 아니면 "NO"를 출력하는 문제 문자열 a의 소문자를 대문자로 0개 이상 바꿀 수 있음. 문자열 a의 소문자를 모두 제거. a = AbcDE, b = ABDE일 때, ABcDE로 b -> B로 바꾼 뒤, 소문자를 모두 제거하면 ABDE가 되므로 b를 만들 수 있음. Dynamic programming을 사용해서 품. 처음에는 대소문자 상관없이 a의 j번째 문자열 = b의..

https://www.hackerrank.com/challenges/max-array-sum/problem Max Array Sum | HackerRank Find the maximum sum of elements in an array. www.hackerrank.com 풀이 입력으로 정수로 구성된 arr를 받을 때, 이웃하지 않은 element와의 최대합을 구하는 문제 n1, n2, n3 3개만 있고 swap해가면서 정답을 구할 수 있음. 보통 dp[i] = i번째 원소까지 봤을 때 최대합 으로 생각해 문제를 접근 n2를 초기화할 때 arr[1]로 하지 말고 max(2번째 원소까지) 음수 값도 존재하기 때문에, i번째 원소가 최대인 경우도 있음. max 값을 update할 때 자기 자신이 최대인 경우도..

https://www.hackerrank.com/challenges/reverse-shuffle-merge/problem Reverse Shuffle Merge | HackerRank Given a string, find the lexicographically smallest substring that satisfies the given conditions. www.hackerrank.com 풀이 입력으로 문자열 s를 받을 때 아래 조건을 만족하는 알파벳 순으로 가장 앞선 문자열 A를 찾는 문제 s \in merge( reverse(A) , shuffle(A) ) merge 연산은 파라미터로 두 개의 string을 받는데, 각 string의 입력 순서만 맞으면 됨. merge( 'abac', 'bcbc'..

https://www.hackerrank.com/challenges/common-child/problem Common Child | HackerRank Given two strings a and b of equal length, what's the longest string (s) that can be constructed such that s is a child to both a and b? www.hackerrank.com 풀이 입력으로 두 개의 string이 주어졌을 때 공통된 child의 최대 길이를 구하는 문제 child : string에서 문자를 1개 이상 삭제한 결과물 ex) s1 = ABCD, s2 = ABDC -> longest common child : ABC or ABD ex) s1 ..

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..