Portfolio

문제

Implement a SnapshotArray that supports the following interface:

SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.

void set(index, val) sets the element at the given index to be equal to val.

int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.

int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example 1:


Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Constraints:

1 <= length <= 50000

At most 50000 calls will be made to set, snap, and get.

0 <= index < length

0 <= snap_id < (the total number of times we call snap())

0 <= val <= 10^9

풀이

은찬


class SnapshotArray{
    constructor(length){
        this.snapshots = new Map();
        this.array = new Map();
        this.snapId = 0;
    };

    set(index, val) {
        this.array.set(index, val);
    };

    snap() {
        this.snapshots.set(this.snapId, new Map(this.array));
        
        return this.snapId++;
    };

    get(index, snap_id) {
        if(this.snapshots.get(snap_id).has(index)){
            return this.snapshots.get(snap_id).get(index);
        }
        
        return 0;
    };
}

zl존코테전사재영

1. 메모리 터짐.


/**
 * @param {number} length
 */

var SnapshotArray = function (length) {
  this.arr = new Array(length).fill(0);
  this.snapshotArr = [];
};

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
SnapshotArray.prototype.set = function (index, val) {
  this.arr[index] = val;
};

/**
 * @return {number}
 */
SnapshotArray.prototype.snap = function () {
	return this.snapshotArr.push([...this.arr]) - 1;
};

/**
 * @param {number} index
 * @param {number} snap_id
 * @return {number}
 */
SnapshotArray.prototype.get = function (index, snap_id) {
  return (snap_id < this.snapshotArr.length) ? this.snapshotArr[snap_id][index] : 0
};

결국 답지를 봤는데, 이건 Map 객체의 특성을 알아야 풀 수 있는 문제더라.

라고 생각했었는데, 살펴본 결과, Map의 경우 메모리가 오히려 많이 든다는 이야기도 있더라.

따라서, 내가 문제를 잘못 푼 게 아닐까 고민했는데, 이유를 발견했다.

그 이유는, 결과적으로 Array로 초기화할 때, 수정되지 않는 0인 값들을 계속해서 고정해서 메모리에 담고 있었던 것.

따라서 그냥 객체로 넣어준 결과, 잘 동작한다.

결과


/**
 * @param {number} length
 */

var SnapshotArray = function (length) {
  this.obj = {};
  this.snapshotArr = [];
};

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
SnapshotArray.prototype.set = function (index, val) {
  this.obj[index] = val;
};

/**
 * @return {number}
 */
SnapshotArray.prototype.snap = function () {
	return this.snapshotArr.push({...this.obj}) - 1;
};

/**
 * @param {number} index
 * @param {number} snap_id
 * @return {number}
 */
SnapshotArray.prototype.get = function (index, snap_id) {
  return this.snapshotArr[snap_id][index] || 0
};

효성


var SnapshotArray = function(length) {
    this.arr = [];
    this.snapMap = new Map();
    this.snapCnt = 0;
};

SnapshotArray.prototype.set = function(index, val) {
    this.arr[index] = val;
};

SnapshotArray.prototype.snap = function() {
    this.snapCnt++;
    let snap_id = this.snapCnt-1;
    let snapshot = [...this.arr];
    this.snapMap.set(snap_id, snapshot);
    return snap_id; 
};

SnapshotArray.prototype.get = function(index, snap_id) {
    const snapshotArr = this.snapMap.get(snap_id);
    return snapshotArr[index] === undefined ? null : snapshotArr[index];
};

Snapshot Array

문제

풀이

1. 메모리 터짐.

결과