Frequency Queries javascript로 풀기

/*

You are given q queries. Each query is of the form two integers described below:

당신에게 q개의 쿼리가 주어진다. 각각의 쿼리는 아래에 설명된 2개의 정수 형태이다.

 

- 1 x : Insert x in your data structure.

- 1 x : x를 자료구조에 삽입한다. 

 

- 2 y : Delete one occurence of y from your data structure, if present.

- 2 y : 자료구조에서 y 항목을 삭제한다(값이 존재하는 경우).

 

- 3 z : Check if any integer is present whose frequency is exactly z. If yes, print 1 else 0.

- 3 z : 만약 어떠한 정수가 z에 존재하는 경우 1을, 아니면 0을 출력한다. 

 

The queries are given in the form of a 2-D array queries of size q where queries[i][0] contains the operation, 

쿼리는 q만큼의 크기를 가진 2차원 배열로 주어지며, queries[i][0]은 연산을 포함하고

 

and queries contains the data element. For example, you are given array. The results of each operation are:

데이터 항목을 포함하고 있다. 예를들어, 아래와 같은 배열 이 주어지면 결과는 각각 아래와 같다.

배열

[(1,1).

(2,2),

(3,2),

(1,1),

(1,1),

(2,1),

(3,2)]

 

Operation   Array   Output

(1,1)       [1]

(2,2)       [1]

(3,2)                   0

(1,1)       [1,1]

(1,1)       [1,1,1]

(2,1)       [1,1]

(3,2)                   1

 

-- 풀이과정 --

걍 겁나 쉽게 넣을때 넣고 뺄때 빼고 출력할때 출력하면 될 것 같은데??

 

-> 생각해보니 데이터를 넣는게 스택으로 넣는거였다.

스택으로 넣는 경우 각 요소마다 고유한 index를 가지기 때문에 이부분을 어떻게 처리하는지가 관건이 되겠다.

아이디어1 

    딕셔너리에 추가할때 연결리스트 형태로 만든다.

    -> 갯수가 너무 많아서 안될것 같음.

 

--> 문제를 다시 읽어보니 내가 해석을 잘못했다.

 

- 1 x : Insert x in your data structure.

- 1 x : x를 자료구조에 삽입한다. 

 

- 2 y : Delete one occurence of y from your data structure, if present.

- 2 y : 자료구조에서 y 항목을 삭제한다(값이 존재하는 경우).

 

- 3 z : Check if any integer is present whose frequency is exactly z. If yes, print 1 else 0.

- 3 z : 만약 어떤 값의 빈도수가 z인 경우 1을, 아니면 0을 출력한다. 

 

이거였다.

 

당연히 개삽질

 

스택은 의미없다.

 

1인경우 딕셔너리에 x를 넣어준다.

    값이 있으면 +1을, 없으면 =1을 준다.

    해당 값의 빈도수를 que 딕셔너리에 저장한다.

2인 경우 딕셔너리에서 y를 찾아 -1해준다.

    값이 있으면 -1을, 없거나 0이면 0을 해준다.

    해당 값의 빈도수를 que 딕셔너리에 저장한다.

3인 경우 que딕셔너리에서 해당 z를 찾는다.

    값이 없거나 0인경우, 답변 배열에 0 추가

    값이 있는 경우 답변 배열에 1 추가

    특정 케이스에서 에러가 발생한다.

 

몇일동안 지랄발광해도 못풀었고 결국 어떤 외국인 고인물의 유튜브를 보고 답을 찾았다.

 

내가 틀린 이유는

 

방법은 맞았지만 빈도수를 카운트 하는 계산식이 틀렸던 것이다.

 

우선 답을 베껴서 풀었지만 다음에 솔플로 다시 풀어보아야 겠다.

*/

// var queries = [[1, 3],[2, 3],[3, 2],[1, 4],[1, 5],[1, 5],[1, 4],[3, 2],[2, 4],[3, 2]]

var queries = [[1, 5],[1, 6],[3, 2],[1, 10],[1, 10],[1, 6],[2, 5],[3, 2]];

const numbers = {};

const counts = {};

 

const results = [];

 

queries.forEach(([operation, number]) => {

    switch (operation) {

        case 1 :

            numbers[number] = (numbers[number] || 0)

            if(numbers[number] > 0){

                counts[numbers[number]] -=1;

            }

            numbers[number] += 1;

            counts[numbers[number]] = (counts[numbers[number]] || 0) + 1;

            break

        case 2 :

            if(numbers[number] > 0){

                counts[numbers[number]] -= 1;

                numbers[number] -= 1;

                counts[numbers[number]] = (counts[numbers[number]] || 0) + 1;

            }

            break;

        case 3 :

            results.push(

                counts[number] > 0 ? 1 : 0

            );

            break;

    }

    console.log(numbers);

})

 

console.log(results) ;