[분석] Codility - MaxCounters - Javascript
Codility 연습문제 > MaxCounters > Javascript
모든 교대 작업을 완료 후 카운터를 1씩 늘리며 그중 가장 최대 값을 구하는 문제.
실제 문제의 저작권은 Codility 에 있으므로 전체 문제의 내용은 Codility 페이지를 방문해 확인하세요.
[문제 및 조건]
처음에는 0으로 설정된 N 개의 카운터가 제공되며 두 가지 가능한 작업이 주어집니다.
- 증가 X: 카운터 X 가 1씩 증가한다.
- 최대 카운터: 모든 카운터는 모든 카운터의 최댓값으로 설정된다.
- M 개의 정수로 구성된 비어있지 않은 배열 A가 제공되며, 이 배열은 연속 작업을 나타낸다.
- A [K] = X, 즉 1 ≤ X ≤ N이면 연산 K는 증가 (X).
- A [K] = N + 1이면 작업 K는 최대 카운터이다.
- 예를들어, N = 5, A = [3, 4, 4, 6, 1, 4, 4] 가 주어지면 각 연속 카운터 값은 다음과 같다.
(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)
[분석]
- 처음 주어지는 N의 값은 카운터를 증가시킬 연속 잡업의 배열이다.
- A[K] = N + 1 즉, 전체 길이보다 크면 카운터가 가장 큰 값으로 모든 작업의 카운트가 적용된다.
- 배열 A의 요소만큼 작업을 수행하고 마지막 카운터 배열을 반환한다.
- N, M
[풀이]
- N의 값을 이용해 카운터 상태를 저장할 배열을 만든다.
- A[K] = N + 1 이면 전체 카운터 배열에서 가장 큰 카운터를 찾아 전부 적용한다.
- N 및 M 은 1 ~ 100,000 범위의 정수이다.
- 배열 A의 각 요소는 1 ~ N + 1 범위이다.
- 결과값뿐만 아니라 성능을 측정하는 문제로, 불필요한 2중 반복문을 피해야 한다.
function solution(N, A) {
// 실제 카운터를 증가할 작업만 추출한다.
const tasks = A.filter(val => val <= N + 1);
// 카운터 배열을 만든다.
const result = new Array(N).fill(0);
let maxCount = 0;
// tasks 에서 최소값이 N + 1 인 경우 바로 카운터가 증가하지 않은 result를 반환
if (Math.min(...tasks) === N + 1) {
return result;
}
// tasks 를 반복하면서 카운터 횟수를 증가시킨다.
for (let i = 0; i < tasks.length; i++) {
const index = tasks[i] - 1;
if (index === N) {
// map, new Array(N).fill(maxCount) 보다 for 를 사용하는게 더 빠르다
for (let j = 0; j < result.length; j++) {
result[j] = maxCount;
}
continue;
}
const count = result[index] + 1;
result[index] = count;
// maxCount 값을 수정한다.
if (count > maxCount) {
maxCount = count;
}
}
return result;
}
for 반복문안에 for 반복문을 사용해 테스트를 통과했습니다. 퍼포먼스 테스트 전부 통과했지만 다른 방법으로 다시 시도해봤습니다.
function solution(N, A) {
// 카운터 배열을 만든다.
const result = new Array(N).fill(0);
let maxCount = 0;
let maxQueue = 0;
// A 를 반복하면서 카운터 횟수를 증가시킨다.
for (let i = 0; i < A.length; i++) {
const index = A[i] - 1;
// 즉 전체 카운터를 가장 높은 카운터로 동일하게 적용해야 한다.
if (index === N) {
// 가장 높은 카운터의 수를 찾아 임시 저장하자
maxQueue = maxCount;
}
// 유효 범위 안에서
else if (0 <= index && index < N) {
// 현재 카운터와 임시 max 카운터 값에 + 1 한 값중 최대값을 적용한다.
result[index] = Math.max(result[index] + 1, maxQueue + 1);
maxCount = Math.max(result[index], maxCount);
}
}
return result.map(val => Math.max(val, maxQueue));
}
[마치며]
MaxCounters 문제는 2중 for 반복문을 사용했고 두 번째는 Math.max()를 사용했지만 시간 복잡도 O(N + M)으로 동일한 성능을 보여주고 있습니다. 100% 통과는 했지만 좀 더 시간 복잡도를 줄이는 방법을 고민해 봐야겠습니다.
Leave a comment