문제 https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/ DNS 시퀀스는 A, C, G, T로 나타낼 수 있고 각각의 impact factor는 1, 2, 3, 4이다. P, Q 리스트는 각각 시작과 끝의 정보를 가진다고 생각하면 된다. 만약 CAGCCTA라는 DNS 시퀀스가 주어질 때 P[0] = 2, Q[0] = 4라면 DNS 시퀀스 중 2~4에 해당하는 값이 탐색 범위이다. (CAGCCTA) 탐색 범위 중 가장 작은 impact factor를 가지는 값을 찾아서 반환하면 된다. 문제 풀이 prefix sum으로 풀 수 있지만, 예외 처리로도 해당 문제를 풀 수 있다. 코드 def solution(S, P, Q..
문제 https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/ 리스트의 값이 순열인지 확인하는 문제이다. 문제 풀이 Missing Integer와 동일한 방식으로 풀면 된다. 코드 def solution(A): sort = sorted(A) check_num = 1 for num in sort: if num == check_num: check_num += 1 return 1 if len(A) == check_num - 1 else 0
문제 https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/ 리스트가 주어지면, 리스트의 존재하지 않는 값을 찾거나 리스트에 값이 모두 존재하는 경우에는 다음의 수를 반환한다. 리스트에 음수만 존재하는 경우에는 1을 반환한다. 문제 풀이 정렬하지 않고 문제를 풀려고 했을때는 체크 리스트를 활용하고, 코드도 보기 흉하게 변했다. 하지만 정렬을 사용하면 아주 간단한게 문제를 해결할 수 있다. 코드 def solution(A): sort = sorted(A) lost = 1 for num in sort: if num == lost: lost += 1 return lost
문제 https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/ 리스트의 값이 N이하 일 경우에는, 해당하는 인덱스의 값을 1 증가시키고 N보다 큰 값인 경우에는 모든 인덱스 값을 현재 값의 max로 변경한다. 문제 풀이 각 인덱스에 값을 추가하다가, N보다 큰 값이 발생한 경우 answer = max(answer) * N로 처리하였더니 효율성을 통과하지 못하였다. def solution(N, A): answer = [0] * N for idx in A: print(answer) if idx > N: answer = [max(answer)] * N else: answer[idx - 1] += 1 return answer 코..
문제 https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/ 개구리가 가고자 하는 위치가 X라면, X에 도달하기 위해 필요한 모든 구간을 거쳐야 한다. 문제 풀이 카운트와 체크 리스트를 활용하여서 문제를 풀면 쉽게 풀 수 있다. 코드 def solution(X, A): check = [False] * X cnt = 0 for i in range(len(A)): if not check[A[i] - 1]: check[A[i] - 1] = True cnt += 1 if cnt == X: return i return -1 지나온 구간을 확인하기 위해 체크리스틀 통해 확인한다. 카운트를 활용해 카운트 값이 가고자 하는 위치와..
문제 https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/ 배열에 다섯개의 값들이 있으면 각 구간 별로 나누어 값을 합산 후에 차를 계산하여 가장 작은 차가 되는 값을 찾는 문제이다. 문제 풀이 처음에는 list를 슬라이싱하여 문제에 접근하였다. 슬라이싱으로 인한 오버헤드가 그렇게 큰지는 처음 알았다. def soultion(A): min_diff = None for i in range(len(A) - 1): diff = abs(sum(A[:i + 1]) - sum(A[i + 1:])) if min_diff is None: min_diff = diff else: min_diff = min(min_diff, diff..
문제 https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/ 배열에 있는 원소들의 수는 N이고 그 중 없는 원소를 찾아야 한다. 예를 들어 1, 2, 3, 5라면 빠진 수는 4이다. 문제 풀이 Counter를 활용하면 문제를 쉽게 해결할 수 있다. 코드 from collections import Counter def solution(A): check = [num + 1 for num in range(len(A) + 1)] return list(Counter(check) - Counter(A))[0]
