2016년 5월 23일 월요일

[Algorithm] Codility Lesson 3 - TapeEquilibrium

 비어있지 않은 배열 A는 N개의 정수로 구성되어 있다. 배열 A는 테잎의 숫자들을 나타낸다.

 0 < P < N 인 정수 P는 테잎을 비어있지 않은 두 파트로 나눈다:
 A[0], A[1], ..., A[P − 1], A[P], A[P + 1], ..., A[N − 1].

 두 파트간의 차이 값을 구하는 식은 :
 |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

 다시 말하면, 첫 파트의 합계와 두번째 파트의 합계 차이값의 절대값이다.

 예를 들어 다음과 같은 배열 A가 있다면:
 A[0] = 3
 A[1] = 1
 A[2] = 2
 A[3] = 4
 A[4] = 3

 4가지 방법으로 나눌 수 있다.:
 P = 1, 차이 = |3 − 10| = 7
 P = 2, 차이 = |4 − 9| = 5
 P = 3, 차이 = |6 − 7| = 1
 P = 4, 차이 = |10 − 3| = 7

 함수 작성:
 int solution(int A[], int N);

 N 개의 정수로 구성된 비어있지 않은 배열 A, 차이값의 최소값을 리턴한다.

 예를 들어
 A[0] = 3
 A[1] = 1
 A[2] = 2
 A[3] = 4
 A[4] = 3
 가 주어진다면, 상술 한 바와 같이 함수는 1을 리턴하게 된다.

 가정:
 N 은 [2..100,000] 범위의 정수
 배열의 각 요소는 [−1,000..1,000] 범위의 정수

 복잡도 :
 최악의 시간복잡도는 O(N)
 최악의 공간복잡도는 O(N) (입력값을 위한 공간 제외)
 배열의 요소는 수정 가능하다.



https://codility.com/demo/results/trainingVW44CT-URM/

댓글 없음:

댓글 쓰기