Memo/코테
[Codility] TapeEquilibrium
연로그
2021. 4. 21. 15:48
반응형
문제: app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/
TapeEquilibrium coding task - Learn to Code - Codility
Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.
app.codility.com
처음에 죄다 타임아웃 에러가 나서 50점도 안나와서 깜짝 놀랐는데 깜빡하고 System.out.println()을 안 지워준거였다...
어쩐지 시간 복잡도가 O(N^2)가 나올리가 없는데 ㅋㅋ ㅠㅠㅠ
정답률 92 코드
class Solution {
public int solution(int[] A) {
int sum = 0;
int sumOfAll = 0;
int lengthOfA = A.length;
int min = 1001;
int cal = 0;
for(int a:A) {
sumOfAll += a;
}
for(int i=0;i<lengthOfA-1;i++) {
sum += A[i];
sumOfAll -= A[i];
cal = Math.abs(sum-sumOfAll);
min = min>cal?cal:min;
}
return min;
}
}
요소가 2개인 경우에 틀렸다.
lengthOfA-1 미만인 경우에만 for문을 돌다보니...
2개인 경우를 추가했다!
아니면 for문의 범위를 바꾸는 방법도 있다.
1부터 시작하고 A[i]가 아니라 A[i-1]에 대해서 계산한다던가의 식으로!
class Solution {
public int solution(int[] A) {
int sum = 0;
int sumOfAll = 0;
int lengthOfA = A.length;
int min = 1001;
int cal = 0;
if(lengthOfA==2) {
return Math.abs(A[0]-A[1]);
}
for(int a:A) {
sumOfAll += a;
}
for(int i=0;i<lengthOfA-1;i++) {
sum += A[i];
sumOfAll -= A[i];
cal = Math.abs(sum-sumOfAll);
min = min>cal?cal:min;
}
return min;
}
}
반응형