본문 바로가기

Problem Solving/Codility6

[ Codility ] MaxProductOfThree - python 개념 Lesson 6. Sorting 두 번째 문제 문제요약 입력으로 주어진 정수 배열에서 숫자 3개를 곱한 값 중 최대를 리턴하라 첫번째 접근(효율성 고려X) 문제에 충실히 만들수 있는 모든 인덱스 조합을 만들고, 그 조합대로 값을 곱한 뒤 최대일 경우 max-value값을 갱신해주는 코드(3개니까 당연히 3중 for문을 돌고, 시간복잡도는 O(N**3)이상) def solution(A): max_v = A[0]*A[1]*A[2] for i in range(len(A)-2): for j in range(i+1, len(A)-1): for k in range(j+1,len(A)): if A[i]*A[j]*A[k]>max_v: max_v = A[i]*A[j]*A[k] return max_v 두번째 접근(통.. 2021. 6. 18.
[ Codility ] Distinct - python 개념 Lesson 6. Sorting 첫 번째 문제 문제요약 N개의 정수를 원소로 갖는 배열A가 입력으로 주어질 때, 원소들의 중복을 제외한 총 개수를 리턴하라 첫 번째 접근 (효율성 고려X, 통과는 O) 파이썬 내장함수를 이용한 풀이(set로 중복 제거한뒤 그 개수만 리턴하는 코드) # 방법 1 def solution(A): return len(list(set(A))) # 방법 2 - 굳이 list를 안해도 돼 ㅎㅁㅎ def solution(A): return len(set(A)) 생각보다 너무 빨리 대충 푼 것 같은 느낌에 set 쓰지 않고 푸는 다양한 방식을 찾아보기로 했다 두 번째 접근 (효율성X) 처음 파이썬을 배웠다면 썼을 것 같은 코드로 문제에 충실하게 짠 코드. A를 쭉 돌다가 지금까지 나.. 2021. 6. 18.
[ Codility ] PassingCars - python 개념 Lesson 5. Prefix Sums 네 번째 문제 문제요약 0,1로만 이루어진 배열A가 입력으로 주어짐. 0은 동쪽으로 가는 차, 1은 서쪽으로 가는 차일때 서로 마주칠 수 있는 케이스는 얼마나 되는지 리턴하는 문제. 예시) [0,1,0,1,1] => (0,1),(0,3),(0,4),(2,3),(2,4) 5개 => 5리턴 첫번째 접근( 효율성 고려X ) 문제에 충실하게, 앞에서부터 순회하다가 0이 나오면 그 뒤에 있는 1의 개수를 구해 더해나가는 방식 def solution(A): cnt = 0 for i in range(len(A)-1): tmp = 0 if A[i] == 0: tmp += A[i+1:].count(1) cnt += tmp return cnt 답은 맞지만 역시 타임아웃. for.. 2021. 6. 17.
[ Codility ] MinAvgTwoSlice - python 개념 Lesson 5. Prefix Sums 세 번째 문제 문제요약 n개의 원소를 갖는 리스트가 주어지면, 0부터 n-1사이에서 두 수를 뽑아 작은 값(P)를 시작인덱스, 큰 값(Q)를 끝인덱스로 정해 A[P:Q+1]에 해당하는 리스트를 슬라이스라고 한다. 만들 수 있는 모든 슬라이스 중 슬라이스 내부 원소들의 평균이 가장 낮을때의 P값(시작인덱스)를 리턴. 첫 번째 접근(효율성 고려X) def solution(A): n = len(A) min_v = sum(A)/n r = 0 comb = [(i,j) for i in range(n-1) for j in range(i+1,n)] for pair in comb: new_v = sum(A[pair[0]:(pair[1]+1)])/(pair[1]-pair[0]+.. 2021. 6. 16.
[ Codility ] CountDiv - python 개념 Lesson 5. Prefix Sums 첫 번째 문제 문제요약 입력으로 정수 A, B, K가 주어졌을 때 정수 A부터 정수 B(를 포함해서) 사이에 있는 정수들 중 K로 나누어 떨어지는 수들의 총 개수를 리턴하라 첫번째 접근(효율성 고려X) 문제에서 풀이한 방식 그대로 코드 구현 def solution(A, B, K): sn = A # 01 starting number를 A로 설정 cnt = 0 while sn 2021. 6. 15.
[ Codility ] GenomicRangeQuery - python 개념 Lesson 5. Prefix Sums 두 번째 문제 문제요약 A,C,G,T 네 종류의 dna 시퀀스가 있고, 각각 1,2,3,4 의 impact factors를 갖고 있음. 네 알파벳이 섞인 문자열 S와 시작 인덱스 범위를 원소로 갖는 리스트 P, 마지막 인덱스 범위를 원소로 갖는 리스트 Q가 입력으로 주어짐. P와 Q의 동일 인덱스 값이 각각 문자열에서 확인할 인덱스의 시작범위와 끝 범위를 의미함. 처음 주어진 문자열에서 P,Q에 주어진 범위 인덱스만을 볼 때 가장 impact factor가 작은 값을 리스트에 담아 리턴하면 됨. ( 결과적으로 리스트에는 P 또는 Q의 원소 개수 만큼 값이 들어있음 ) 첫번째 접근(효율성 고려X) 문제에서 풀이한 방식 그대로 코드 구현 def solution(S.. 2021. 6. 15.

티스토리툴바