Tasks
https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/
- N size의 배열을 counter라 하고, A의 각 element들이 가리키는 k번째의 counter 갯수를 1 올려주면 된다. 이때, k가 N+1인 경우 모든 counter의 값을 최대값으로 update 해 주어야 한다.
- N과 A의 size가 최대 100,000이므로, 문제에서 하라는대로 정직하게 구현하면 시간초과가 난다. (A의 모든 k가 N+1이라고 가정해보자. 그러면 매 번 모든 counter들을 update해 주어야 하므로 총 N^2의 시간이 걸리기 때문이다.
내 풀이
for문을 통해 주기적으로 업데이트 하다가 66%라는 처참한 결과를 맞이 했다.
그 이유는 시간 복잡도를 고려하지 않고 풀어서 그런 것이었다.
N이 무수히 커진다면 그 시간복잡도가 매우 크므로, 그를 해소하기 위해
한번에 업데이트를 했어야 했다.
관련된 강의도 보고, 구글링도 했지만 이렇다 하고 옳은 정답이 없어서 지피티에 물어봤다.
지피티 말씀
매번 ans 배열의 최대값을 구하는 것이 비효율적입니다. 대신에, 최대값을 구하는 시점에서 따로 저장하고, ans 배열을 한 번에 업데이트하는 것이 더 효율적입니다.
ans 배열을 업데이트할 때마다, ans 배열의 최대값도 업데이트합니다. 이를 통해, 모든 값이 최대값으로 업데이트될 때마다 ans 배열의 최대값을 갱신합니다.
function solution(N, A) {
let ans = Array(N).fill(0)
let max = 0;
let prevMax = 0;
for (let i = 0; i < A.length; i++) {
const val = A[i];
// 현재 순회하는 인덱스가 N보다 작거나 같으면 1을 증가시키면서 max값을 계속 가장 큰 값으로 업데이트 해줌
// 여기에서 else문에 걸려 만약 N보다 크다면 가장 컸던 값을 prevMax에 저장
if (val <= N) {
ans[val - 1] = Math.max(ans[val - 1], prevMax) + 1;
max = Math.max(max, ans[val - 1]);
} else {
prevMax = max;
}
}
// 위에 포문이 다 돌아간 후에, ans배열을 다시 순회하면서
// 각 인덱스가 preveMax보다 작다면 prevMax로 바꿔주고 그렇지 않다면 원래 갖고 있던 값을 쓰도록 해줌
for (let i = 0; i < ans.length; i++) {
ans[i] = Math.max(ans[i], prevMax);
}
return ans;
}이 코드도 N개의 카운터를 가진 배열 ans를 생성합니다. 그리고 작업 배열 A를 순회하면서 작업을 수행합니다. 작업 값이 N보다 작거나 같으면, 해당 작업에 해당하는 인덱스의 값을 1 증가시킵니다. 이 때, 이전에 처리된 작업 중에 가장 큰 값을 prevMax 변수에 저장해 둡니다. 그리고 ans 배열을 업데이트하면서, 이전에 처리된 작업 중 가장 큰 값과 현재 값의 합 중에서 큰 값을 해당 인덱스에 저장합니다. 그리고 max 변수를 이용하여 현재까지 가장 큰 값을 구합니다.
작업 값이 N+1이면, 이전에 처리된 작업 중 가장 큰 값을 prevMax 변수에 저장합니다. 이렇게 하면 ans 배열을 한 번에 업데이트하면서 최대값을 갱신할 수 있습니다.
작업을 모두 수행한 후, ans 배열을 다시 순회하면서 prevMax 값을 이용하여 ans 배열의 값들을 갱신합니다. 이렇게 하면 모든 카운터의 값을 가장 큰 값으로 바꾸어야 하는 작업에서도 ans 배열을 한 번만 업데이트하므로, 시간 복잡도를 크게 줄일 수 있습니다.
이 코드의 시간 복잡도는 O(N+M)입니다.
