Codilty [ Lesson 7 | Stacks and Queues ] Fish - JavaScript

Sohyeon Bak·2022년 3월 1일

Codility

목록 보기

15/19

문제

You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.

The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.

Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:

0 represents a fish flowing upstream,
1 represents a fish flowing downstream.
If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:

If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.
We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.

For example, consider arrays A and B such that:

A[0] = 4 B[0] = 0
A[1] = 3 B[1] = 1
A[2] = 2 B[2] = 0
A[3] = 1 B[3] = 0
A[4] = 5 B[4] = 0
Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.

Write a function:

function solution(A, B);

that, given two non-empty arrays A and B consisting of N integers, returns the number of fish that will stay alive.

For example, given the arrays shown above, the function should return 2, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [0..1,000,000,000];
each element of array B is an integer that can have one of the following values: 0, 1;
the elements of A are all distinct.

문제해석

2개의 배열이 주어진다.
A 배열에는 물고기들의 크기가 주어지고, B 배열에는 물고기들이 움직이는 방향을 알려준다.
물고기들은 자신의 방향대로 흘러가다가 만난 물고기 중 자신보다 작은 물고기를 먹고 없애버린다. 모든 물고기들이 지나가고 남게 되는 물고기의 수를 구하는 문제이다.

B 배열에는 2가지가 주어지는데, 0은 상류로 흘러가고 1은 하류로 흘러간다. B 배열에서 0보다 1의 인덱스 값이 작으면 무조건 0과 1의 물고기는 만난다. 그때 A 배열에서 각 물고기의 크기를 보고 더 작은 물고기는 없애고 다음 인덱스를 비교해야한다.

문제풀이

stack문제를 풀어야 할 때 stack에 무엇을 넣어 줘야하는지 설정하는 것이 중요하다. 이 문제에서는 stack에 비교를 통해 살아남은 물고기의 인덱스를 stack에 넣어줘야한다. 그리고 인덱스 값을 증가하면서 물고기를 비교하는데 살아남은 물고기보다 비교해야하는 물고기의 인덱스가 더 커야한다. 이유는 어짜피 상류로 흘러가는 물고기보다 하류로 흘러가는 물고기의 인덱스가 더 크면 만날 이유가 없기 때문에 크기 상관없이 두 물고기는 모두 살아남기 때문이다.

stack에는 처음에 0을 넣고, 비교할 인덱스는 1로 시작한다.
B[1]이 0(상류로 올라가는 물고기), B[0]이 1(하류로 흘러가는 물고기)라면 A[1]이 A[0]를 비교해 A[1]이 크면 stack에 남아있는 물고기를 없앤다.
그렇지 않다면 모두 기존 물고기가 크거나 다음 물고기를 만나지 않았기 때문에 비교할 인덱스를 1개씩 높여준다.

코드

function solution(A, B) {
    // write your code in JavaScript (Node.js 8.9.4)
    let leng = A.length;
    let stack = [];
    let n = 1

    stack.push(0)
    while(n<leng){
        if(B[n]==0 && B[stack[stack.length-1]]==1){
            if(A[n]>A[stack[stack.length-1]]){
                stack.pop()
            }else{
                n++
            }
        }else{
            stack.push(n);
            n++;
        }
    }

    return stack.length
}