Archive

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

programmers.co.kr/learn/courses/30/lessons/62049 코딩테스트 연습 - 종이접기 직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다. 먼저 오른쪽 절반을 왼쪽으로 접습니다. 다시 오른쪽 절반을 왼쪽�� programmers.co.kr 후기 규칙을 정확히 찾아야 함. 처음 test case 1, 2, 3만 봤을 때, 이전 접은것이 2번 반복 + [1]로 코딩했으나 틀림. 규칙은 이전 값 + [0] + 이전 값의 xor 이었음. 재귀함수보다 for문으로 answer를 덮어쓰는 방법으로 구현. 파이썬 코드 def solution(n): answer = [] for i in range(n): answ..

www.hackerrank.com/challenges/climbing-the-leaderboard/problem Climbing the Leaderboard | HackerRank Help Alice track her progress toward the top of the leaderboard! www.hackerrank.com 후기 문제 입력 조건을 꼼꼼히 봐야함. scores의 경우 내림차순으로(100, 90, 80, ...) 입력받고, alice의 경우 오름차순(50, 60, 79, ...)으로 입력받는다. 처음에는 입력 조건 제대로 안보고 scores list를 매번 반복문을 통해 순회하며 올바른 등수를 찾았지만, 시간초과 남. 나중에 입력 조건 확인 후, 정렬된 값으로 입력받기 때문에 alice..