L5_CounDiv

Posted on | In |

L5_CounDiv

목차

  • Step 1. 문제 설명
  • Step 2. 풀이
  • Step 3. 결과

Step 1. 문제 설명

양수 A에서 B까지 원소로 구성된 list가 존재한다. K 값이 주어졌을때, K로 나눴을 경우, 나머지가 0인 숫자들의 개수를 return하는 문제다.

A <= i <= B

문제 : https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/

step 2. 풀이

첫번째 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def solution(A, B, K):
    set_AB = set()
	set_K = set()
	
	for i in range(A, B+1):
		set_AB.add(i)
	for j in range(0, B):
		set_K.add(j * K)
		
		if j * K > B:
		   break

	inter_ABK = set_AB & set_K
 
	if A == B == 0:
	   return len(inter_ABK) + 1
	else:
	   return len(inter_ABK)

  1. A에서 B 원소까지 이루어진 집합 생성

  2. 0부터 B까지 K의 곱으로 이뤄진 집합 생성시, 만약 해당 집합이 B보다 크면 거기서 멈춘다

  3. 위에서 만든 집합의 교집합 생성

  4. A,B가 모두 0이면 0을 리턴, 그렇지 않으면 K가 나눌 수 있는 개수 만큼인 해당 집합의 길이를 리턴

정확도는 100점이지만, performance를 0점 맞아서 50점 맞았다 …ㅎ

두번째 풀이

1
2
3
4
5
6
7
8

def solution(A, B, K):
 
	 if A == 0:
		return int(B/K) + 1
	 else:
		return int(B/K) - int((A-1)/K)

최대한 심플하게 풀어보려 노력했다..

  1. A가 0일때, 0부터 B까지 이므로 0도 나머지가 0인 경우에 포함되므로 +1 을 해준다.

  2. A가 0이 아닐때, B의 몫 - (A의 몫 - 1) 을 해줬다. 그 이유는 A도 K로 나눴을 때 나머지가 0일 수 있기 때문이다.

Step 3. 결과

CountDiv