Archive

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의 종료조건으로 활용..

풀이 홀수 입력 -> 0 이전 값을 저장 -> 덮어쓰는 방법 적용. 규칙 찾기가 어려웠는데, 경우의 수를 잘 나누어야 함. f(8)을 예로 들면, 가로 길이가 8일 때, 1, 2, 2, 2, 1로 배치하는 경우가 2가지(위, 아래) 가로 길이가 6 + 새로운 길이 2 붙인다면 -> f(6) x 3 가로 길이가 4 + 가로 길이 4-> f(4) x 2 (1, 2, 1인 경우) 가로 길이가 2 + 가로 길이 6 -> f(2) x 2 (1, ,2, 2, 1인 경우) 가로 길이가 홀수일때는 생각하지 않아도 됨. 짝수인 경우만 생각하기 def solution(n): answer = 1 special = 0 for i in range(2, n+1, 2): answer2 = 3 * answer + special * ..

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

제네릭 프로그래밍 제네릭(generic) : 파라미터의 타입이 나중에 지정되게 해서 재활용성을 높일 수 있는 프로그래밍 스타일. 파이썬은 원래 동적 타이핑(Dynamic Typing)언어이기 때문에 제네릭이 필요 없음. 타입이 표기되지 않기 때문에 특정 변수의 타입을 바로 알기 어려워 가동성이 낮음. 후에 PEP 484에 추가된 타입 힌트(Type Hints)를 통해 제네릭을 사용. PEP 484는 파이썬 3.5부터 사용 가능. 타입 힌트를 통해 함수의 파라미터가 어떤 자료형이 들어가고, 리턴 값이 무엇인지 명시해줌으로써 가독성을 향상시킴. def are_equal(a : int, b : int) -> bool: return a==b 네이밍 컨벤션 Snake case : 각 단어를 &#39;_&#39;로..