[해커랭크] (Data Structures - Arrays) Dynamic Array (javascript)

주어진 조건에 따른 동적 2차 배열을 생성하고 쿼리(q) 상태에 따른 처리 수행
주어진 설명이 이해가 불가능하여 해석법 검색 후 수행함
풀이를 정리하다 보니 HashTable 과 로직이 비슷한 느낌..?

 

규칙 및 조건

• n 개의 빈 배열을 가지는 2차원 arr 이 존재하며, 모든 배열은 0으로 인덱싱 됨
• lastAnswer는 초기값 0 임
• 주어지는 쿼리(queries)는 2개의 타입(q)을 가짐
  • queries는 query를 인자로 가지는 배열
  • query: [q, x, y] (이때 , q는 1 또는 2)
• query 타입별 처리법
  1. Query: 1 x y
     1. idx 는 (x  ⨁ lastAnswer) % n
     2. arr[idx]에 y 값 추가
  2. Query: 2 x y
     
     1. idx 는 (x ⨁ lastAnswer) % n
     2. lastAnswer 에 arr[idx][y % size(arr[idx]) 값을 대입
     3. 새로운 lastAnswer는 answer 배열에 저장
• ⨁ 는 XOR 연산자
  • a ⨁ b  => a ^ b
• size(arr[idx]) 는 arr[idx]의 인자 수
• q = 2 일 때의 구해지는 lastAnswer 값들 (저장된 answer) 을 출력 

 

제한사항

• 1 ≤ n, q ≤ 10⁵
• 0 ≤ x, y ≤ 10⁹ 
• q = 2 는 빈 배열이나 인덱스를 쿼리하지 않음

 

나의 풀이 

• 값 초기화
  • 빈 arr 배열 생성
    •  설명에서는 n개의 빈 배열이라고 하나, n개만큼 생성해도 그 이상의 index가 나오기 때문에 필요할 때 마다 확장시키기로 함
  • answer 배열 생성
  • lastAnswer 초기화
• for loop 로 queries 배열만큼 반복
  • 각 query[q, x, y]로부터 주어진 연산자를 통해 idx 추출
  • q = 1 일 때, arr[idx]에 y 값 추가. (단, arr[idx] 가 없으면 빈배열 생성)
  • q = 2 일 때, arr[idx][y%size(arr[idx])] 값을 lastAnswer에 대입
    • lastAnswer 값을 answer 에 추가

// 생략

/*
 * Complete the 'dynamicArray' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. 2D_INTEGER_ARRAY queries
 */

function dynamicArray(n, queries) {
    // Write your code here
    const len = queries.length;
    let lastAnswer = 0;
    const answer = [];
    const arr = [];
    
    for(let i = 0; i < len; i++) {
      const [q, x, y] = queries[i];
      const idx = (x^lastAnswer)%n;
      
      if (+q === 1) {
        if (!arr[idx]) {
          arr[idx] = [];
        }
        arr[idx].push(y);
      } else {
        const idx2 = y % (arr[idx].length);
        lastAnswer = arr[idx][idx2];
        answer.push(lastAnswer);
      }
    }
    
    return answer;
}

// ... 후략

결과