Archive

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

https://www.hackerrank.com/challenges/pairs/problem Pairs | HackerRank Given N numbers, count the total pairs of numbers that have a difference of K. www.hackerrank.com 풀이 Input : 두 개 숫자의 차이 k, 숫자 배열 arr arr에 있는 두 개의 숫자의 차이가 k인 모든 경우의 수를 구하는게 문제 시간복잡도를 줄이는 문제로, 2중 반복문으로는 통과할 수 없음 -> O(NlogN) 이하 필요 python인 경우, set자료구조에서 교집합을 구할 때의 시간복잡도는 두 개 리스트 길이의 합. O(len(s) + len(t)) set의 자료구조를 사용해 전체 item에 k..

https://www.hackerrank.com/challenges/triple-sum/problem Triple sum | HackerRank Sum of special triplets having elements from 3 different arrays. www.hackerrank.com 풀이 input : 숫자로 구성된 리스트 3개 (a, b, c) a, c의 원소는 b의 원소보다 작은 조건으로 생성할 수 있는 tuple의 개수를 구하는 문제 b의 i번째 원소 bi일 때 len([bi보다 작은 a의 원소]) * len([bi보다 작은 c의 원소])를 구해서 모든 원소 b에 대해 1번 순회하면 됨. [bi보다 작은 a의 원소], [bi보다 작은 c의 원소]를 list comprehension으로 구..

https://www.hackerrank.com/challenges/ctci-ice-cream-parlor/problem Hash Tables: Ice Cream Parlor | HackerRank Help Sunny and Johnny spend all their money during each trip to the Ice Cream Parlor. www.hackerrank.com 풀이 input : 가지고 있는 money, 아이스크림 가격 정보에 대한 list 두 개의 아이스크림 가격의 합이 가지고 있는 money와 일치할 때 아이스크림의 index를 오름차순으로 출력 아이스크림 가격 리스트를 한 번 순회하면서 파이썬의 dictionary를 사용해 , key는 i번째 아이스크림의 가격, value는 ..

풀이 바위 사이의 거리를 이분탐색으로 찾는 문제 변수의 의미 파악이 중요함. left, right의 평균 distance를 구함 -> 결과를 보고 distance +1 이나 distance - 1을 left 혹은 right에 할당함 -> search 영역이 반으로 줄어듬. def solution(distance, rocks, n): answer = 0 rocks.sort() rocks.append(distance) left, right = 0, distance while left 제거할 바위 개수로 count함 distance = (left + right)//2 for current_rock in rocks: # 이전 바위 + distance 안에 현재 바위가 있으면 count 증가 if current_..

풀이 Trie 자료구조 사용하지 않으면 효율성 테스트에서 시간초과. 이전에 map, filter로 풀어봤지만 효율성 테스트 1,2에서 시간초과발생했음. wildcard가 처음에 나오는 경우, 끝에서 나오는경우를 생각해야 함. words를 원래 순서대로 넣은 Trie, 거꾸로 넣은 Trie 2개를 활용. 문제 조건에 중복된 word나 query가 있을 수 있기 때문에, 각각 dictionary를 사용해 이전 값을 저장. class Node(object): def __init__(self, w=None): # 알파벳 하나를 저장 self.word = w # 다음 등장하는 모든 알파벳을 저장 self.children = {} # 단어 끝 알파벳에 단어 길이를 저장(search연산에서 dfs의 종료조건으로 활용..

https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 풀이 방법 먼저 group을 나눠야 함. BFS로 파이썬 list를 사용해 구현. 두 그룹 사이의 높이 차를 구해야 함. dictionary를 사용. key는 (group1, group2) (group1 < group2) value는 두 그룹의 높이 차이 계산을 최소화하기 위해, (0,0)을..