프로그래밍/알고리즘, 프로그래밍 언어
[코딩테스트] Codility 5-1 PassingCars (JavaScript)
제이콥J
2022. 1. 26. 12:48
문제 링크 : https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/
Solution1
정답률 : 100%
시간복잡도 : O(N)
East 방향의 자동차를 east 배열을 선언하여 따로 넣기
특정 East 방향의 자동차보다 큰 자동차들 개수에서, East 방향의 자동차 수를 뺀 수를 count에 더해주기
function solution(A) {
let count = 0;
// 배열 A에서 east 방향의 자동차만 담는 배열을 따로 선언하기
let east = [];
for (let i=0; i<A.length; i++) {
if (A[i]===0) east.push(i);
};
for (let j=0; j<east.length; j++) {
// (전체 수) - (east[j]보다 작은 수) - (east[j]보다 큰 수들 중 east 배열에 속한 수)
let addNum = A.length - (east[j]) - (east.length-j);
count += addNum
}
return count > 1000000000 ? -1 : count;
}
Solution2
정답률 : 100%
시간복잡도 : O(N)
East 방향의 자동차 수를 카운팅한 뒤, West 방향의 자동차를 만나면 result에 East 방향의 자동차 수를 더해주기
function solution(A) {
let result = 0;
let east = 0;
for (let ele of A) {
if (ele === 0) {
east += 1;
} else {
result += east;
}
}
return result > 1000000000 ? -1 : result;
}
반응형