[알고리즘] 시간복잡도, 개구리점프, 빠진숫자찾기, 테이프균형
- 개구리점프 FrogJmp
1
def solution(X, Y, D)
that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y. For example, given: X = 10 Y = 85 D = 30 the function should return 3, because the frog will be positioned as follows:
1
2
3
after the first jump, at position 10 + 30 = 40
after the second jump, at position 10 + 30 + 30 = 70
after the third jump, at position 10 + 30 + 30 + 30 = 100
Write an efficient algorithm for the following assumptions:
1
2
X, Y and D are integers within the range [1..1,000,000,000];
X ≤ Y.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# X위치에 있는 개구리는 한번에 D만큼 점프해서 Y이상 위치로 가려한다.
# 최소 몇 번 점프하면 되는가? N
def solution(X, Y, D):
# # Y = X:
# X += D
# N += 1
# # print(N)
# return N
# 또는
import math
return math.ceil((Y-X)/D)
- 빠진 숫자 찾기 PermMissingElem Find the missing element in a given permutation.
Task description An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
1
def solution(A)
that, given an array A, returns the value of the missing element.
For example, given array A such that:
1
2
3
4
A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
the function should return 4, as it is the missing element.
Write an efficient algorithm for the following assumptions:
1
2
3
N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# N개의 요소들을 돌면서 연속적인 숫자들이 없이 빠진 걸 찾으면 됨.
# 시간복잡도로 보니 O(N^2)으로 풀어도 됨.
# 정렬해주고 나서 한 번만 가자.
# 시간복잡도 = O(NlogN)파이썬정렬 + O(N) => O(NlogN)
def solution(A):
A.sort()
# print(A)
expect = 1
for a in A:
if expect != a:
return expect
expect +=1
# 마지막까지 문제 없었으면 마지막 숫자가 빠진 것
return expect
- TapeEquilibrium Minimize the value |(A[0] + … + A[P-1]) - (A[P] + … + A[N-1])|. Task description A non-empty array A consisting of N integers is given. Array A represents numbers on a tape. Any integer P, such that 0 The difference between the two parts is the value of: |(A[0] + A[1] + … + A[P − 1]) − (A[P] + A[P + 1] + … + A[N − 1])| In other words, it is the absolute difference between the sum of the first part and the sum of the second part. For example, consider array A such that:
1
2
3
4
5
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
We can split this tape in four places:
1
2
3
4
P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7
Write a function:
def solution(A)
that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.
For example, given:
1
2
3
4
5
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
the function should return 1, as explained above.
Write an efficient algorithm for the following assumptions:
1
2
N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# A[0] = 3
# A[1] = 1
# A[2] = 2
# A[3] = 4
# A[4] = 3
# P는 A를 두 파트로 나눈다.
def solution(A):
minDiff:float = float("inf")
left = 0
right = sum(A)
for i in range(len(A)-1):
left += A[i]
right -= A[i]
diff = abs(left-right)
# print(diff)
if minDiff > diff:
minDiff = diff
# print("left", left, "right", right)
# print(minDiff)
return minDiff
#Time Complexity, #시간복잡도, #알고리즘