[코딜리티] codility lesson3 Time Complexity - TapeEquilibrium 100%
문제.
풀이.
설명.
포인터 P 의 위치에 따라 배열을 양분 하고 두 배열 의 차 에서 절대값이 가작 장은 수를 찾아라.
함정. 시간 복잡도를 줄일 수 있는 수학적(산수적) 지식이 필요함.
코딜리티 문제를 풀면서 느낀건 알고리즘 을 짜고 함수를 만들어야 하는 이곳에 자꾸 함수를 가져다가 써서 푸는 사람들이 많다는 것이다.
예전에 기술면접에서 문장을 문자 단위로 역배열 하는 함수를 짜라는 문제가 나온적이 있었다.
추가 조건은 라이브러리를 사용하지 말것 과 연산을 최소화 할 것.
리커시브로 변수 한개 사용해서 만들었다.
면접관 말하길..." 왜 스택 안썼어요? 스택 몰라요? "
스택이 라이브러리가 아니라고 주장하면 할말 없다만.
스택을 쓰면 연산이 최소화 될까? 서버프로그래머 면접관 이라믄서...
떨어졌다.
Programming language:
A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
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:
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
We can split this tape in four places:
- 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:
int solution(int A[], int N);
that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
For example, given:
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
the function should return 1, as explained above.
Assume that:
- 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].
Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
Copyright 2009–2017 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
풀이.
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
26
27
28
29
30
|
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int result = 0;
int setA = 0;
int setB = 0;
int setC = 0;
for( int sumN : A ) setB += sumN;
result = A[0] - (setB - A[0]);
if(result < 0) result *= -1;
for( int i = 0 ; i < A.length-1 ; i++){
setA += A[i];
setB -= A[i];
setC = setA - setB;
if(setC < 0) setC *= -1;
if(result > setC) result = setC;
}
return result;
}
}
| cs |
설명.
포인터 P 의 위치에 따라 배열을 양분 하고 두 배열 의 차 에서 절대값이 가작 장은 수를 찾아라.
함정. 시간 복잡도를 줄일 수 있는 수학적(산수적) 지식이 필요함.
코딜리티 문제를 풀면서 느낀건 알고리즘 을 짜고 함수를 만들어야 하는 이곳에 자꾸 함수를 가져다가 써서 푸는 사람들이 많다는 것이다.
예전에 기술면접에서 문장을 문자 단위로 역배열 하는 함수를 짜라는 문제가 나온적이 있었다.
추가 조건은 라이브러리를 사용하지 말것 과 연산을 최소화 할 것.
리커시브로 변수 한개 사용해서 만들었다.
면접관 말하길..." 왜 스택 안썼어요? 스택 몰라요? "
스택이 라이브러리가 아니라고 주장하면 할말 없다만.
스택을 쓰면 연산이 최소화 될까? 서버프로그래머 면접관 이라믄서...
떨어졌다.
댓글
댓글 쓰기