MaxCounters

/Codility

문제 해석

요약

정수 N과 배열이 하나 주어지는데,
여기서 N은 0으로 가진 카운트 자리수이자 기준이다. 일단, N=5라면 (0, 0, 0, 0, 0)라고 생각하면 된다.
그리고 배열이 하나 주어질 텐데, 각 요소를 기준인 1 ≤ 요소 ≤ N에 맞춰 그 값을 1 카운트 하면 된다. 만약 기준을 넘어가는 값이라면, 현재 카운트 된 최대값을 모든 카운트에 적용해 주어야 한다.

전문

🇰🇷 번역

0으로 초기값이 설정된 N자리 카운터가 주어지고, 두가지 가능한 작업이 있다.

  • increase(X) - 카운터 X는 1씩 증가한다,
  • max counter - 모든 카운터는 최대값으로 설정된다.

정수 M개로 구성된 비어있지 않은 배열 A가 주어진다. 이 배열은 연속된 작업을 나타낸다.

  • 만약 A[K] = X면, 1 ≤ X ≤ N이면 작업 K는 increase(X),
  • 만약 A[K] = N + 1이면, 작업 K는 max counter.
정수 N = 5 그리고 배열 A가 다음과 같다면:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 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)
모든 작업 후 카운터의 값을 계산하는 것이 목표이다.

함수를 작성하시오:
function solution(N, A);

정수 N과 M개의 정수로 구성된 비어있지 않은 배열 A가 주어지면, 카운터의 값을 나타내는 정수 배열을 반환하시오.

다음과 같다면:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

위의 설명에 따르면 함수는 [3, 2, 2, 4, 2]을 반환해야한다.

다음과 같은 가정에 따라 효율적인 알고리즘을 작성하시오:

  • N과 M은 [1..100,000]범위 안의 정수이다;
  • 배열 A의 각 요소는 [1..N+1]범위 안의 정수이다.

🇺🇸 원문

You are given N counters, initially set to 0, and you have two possible operations on them:

  • increase(X) − counter X is increased by 1,
  • max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

  • if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
  • if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
the values of the counters after each consecutive operation will be:

(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)
The goal is to calculate the value of every counter after all operations.

Write a function:

function solution(N, A);

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

  • N and M are integers within the range [1..100,000];
  • each element of array A is an integer within the range [1..N + 1].

🤔 문제 해결 방법 구상

한국어로 번역은 하였으나, 그냥 읽어서는 파악하기 어려웠다.
주어진 예시로 살펴보면 다음과 같다.
주어진 값은 N = 5, A = [3, 4, 4, 6, 1, 4, 4] 두가지.
기준은 1 ≤ 요소 ≤ 5면 1씩 증가하는 increase, 요소 = N + 1이면 최대 카운터로 모두 적용하는 max counter.

A 요소 작동 예시 설명
3 (0, 0, 1, 0, 0) 요소가 범위에 맞으니 3번째 0 + 1
4 (0, 0, 1, 1, 0) 요소가 범위에 맞으니 4번째 0 + 1
4 (0, 0, 1, 2, 0) 요소가 범위에 맞으니 4번째 1 + 1
6 (2, 2, 2, 2, 2) 요소가 N+1이므로, 현재 최대 카운트인 2를 모든 자리에 적용
1 (3, 2, 2, 2, 2) 요소가 범위에 맞으니 1번째 2 + 1
4 (3, 2, 2, 3, 2) 요소가 범위에 맞으니 4번째 2 + 1
4 (3, 2, 2, 4, 2) 요소가 범위에 맞으니 4번째 3 + 1

최종적으로 배열 형태 [3, 2, 2, 4, 2]로 리턴!

  1. N의 길이만큼 0으로 채운 배열을 생성
  2. for loop을 통해 요소와 N범위에 따라 +1 혹은 최대값으로 채우기
  3. 카운터 리턴

코드 구현

function solution(N, A) {
  let counters = Array(N).fill(0);
  let max = 0;

  for(let K in A) {
    const X = A[K];
    if (X <= N) {
      if (counters[X - 1] === max) {
        max++;
      }
      counters[X - 1]++;
    } else if(X === (N + 1)) {
      counters = Array(N).fill(max);
    }
  }
  return counters;
};

결과 분석

Task Score: 77%
Correctness: 100%
Performance: 60%

시간 복잡도는 O(N*M). 공간 복잡도는 O(n)으로 예상한다.

통과하지 못한 이유는 TIMEOUT ERROR로, max_counter작업이 큰 경우들이 통과를 하지 못했다.

🧐 개선

Aㅏ.......이런 시간복잡도가...ㅜㅠ
아마 loop 안에서 최대카운트로 변경하는게 잦아지면 시간복잡도가 커지는 것 같다.

차근 차근 문제를 따라 작성해봐야겠다.

  1. N의 길이만큼 0으로 채운 카운터 배열이 있다.
  2. 필요한 변수

    • max: 현재 최대 카운트 저장
    • laterMax: 후에 한번에 적용시킬 변수 저장
  3. for 문을 돌면서 요소가 1 증가시킬 것인지, 현재 최대 카운트로 변경해야하는지 결정

    • 1을 증가시키는 작업의 경우, 최대카운트 변경 후 1증가라면 laterMax를 반영하여 1증가
    • for문을 도는 시점의 최대 카운트(max) 업데이트
    • 최대 카운트 반영이라면 바로 최대카운트로 변경하는 것이 아니라, laterMax 크기를 저장해둔 현시점의 최대카운트인 max로 업데이트
  4. 최대 카운트를 한번에 적용
  5. 최종 카운터 결과값을 리턴

개선 코드

function solution(N, A) {
  let counters = Array(N).fill(0);
  let max = 0;
  let laterMax = 0;

  for(let K in A) {
    const X = A[K];
    if (X <= N) {
      if (counters[X - 1] < laterMax) {
        counters[X - 1] = laterMax;
      }
      counters[X - 1]++;
      if (max < counters[X - 1]) {
        max = counters[X - 1];
      }
    } else {
      laterMax = max;
    }
  }

  if(laterMax) {
    counters = counters.map(c => c < laterMax ? laterMax : c);
  }

  return counters;
}

개선 결과

Task Score: 100%
Correctness: 100%
Performance: 100%

시간 복잡도가 O(N+M)로 개선되고 모든 테스트 케이스를 통과하였다!

마무리

결과값은 잘 나오는데, 퍼포먼스 테스트를 통과하지 못했다. 여기에는 하나만 개선 코드를 하나만 작성했지만, 여러가지로 문제를 풀어보았는데, 그 문제를 개선하는 과정을 통해 여러가지 테스트를 해볼 수 있는 기회였다.
이번에 Array.prototype.fill()for를 통해 array를 만드는 과정을 테스트해보니, for가 더 빠르게 나오는 편이었다. 이처럼 같은 결과물을 내지만 메소드 별 성능의 차이를 보이는 것에 대해 간단한 테스트도 할 수 있었다.

Reference & Learn More

MDN Array.prototype.fill()
Stack overflow: Most efficient way to create a zero filled JavaScript array?

Tags
Comments