2018-11-17
[JS] Frog Jpm
EASY

개요

0부터 시작하는 N개의 카운터에는 두가지 기능이 있습니다.

  • increase(X) - 카운터 X의 숫자가 1 오릅니다.
  • max counter - N개의 카운터가 가진 숫자 중 가장 큰 수로 모든 카운터를 채웁니다.

길이가 M인 배열이 주어집니다.

  • A[K] = X에서 1<=X<=N이라면 increse(X)를 수행합니다.
  • A[K] = N+1이면 max counter를 수행합니다.

예시

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)

목표는 모든 카운터의 값을 계산하는 것입니다.

문제

integer N이 주어지고, integer M으로 채워진 배열 A가 주어질 때, 카운터들의 값으로 구성된 시퀀스를 반환하세요.

A = [3, 4, 4, 6, 1, 4, 4]일 때, [3, 2, 2, 4, 2]를 반환합니다.

제한

  • N, M은 1 ~ 100,000 범위를 갖는 정수입니다.
  • 배열 A의 각 요소는 1 ~ N+1 범위를 갖는 정수입니다.

풀이

스코어 77% (정확도 100%, 성능 60%)

function solution(N, A) {
  let counter = []
  let max = 0
  
  for (let i = 0; i < N; i++) {
    counter[i] = 0
  }
  
  for (let i = 0; i < A.length; i++) {
    if (A[i] <= N) {
      counter[A[i]-1]++
      if (max < counter[A[i]-1]) {
        max++
      }
    } else {
      counter.fill(max)
    }
  }
  return counter
}

설명

A[i]의 값이 N보다 작거나 같다면 counter[A[i]-1]을 +1 하고, 아니라면(N+1이 들어왔다면) 모든 카운터를 현재 카운터들이 가진 가장 큰 값으로 맞춰야 하는 것에 주목하세요.

아직 카운터의 수가 많을 때 효율적으로 초기화하는 방법을 찾지 못했습니다.