Lesson 7. Stacks and Queues - Fish

1. 문제

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:
  int solution(vector<int> &A, vector<int> &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.

 

살아남는 물고기 수를 구하는 문제.

vector A : 물고기 파워(?)

vector B : 물고기 방향 (up 0 , down 1)

서로 다른 방향의 물고기 만났을 때, 강력한 물고기 한마리만 살아남는다.

 

예시) return 2, 살아 남는 물고기 A[0], A[4]

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

 

2. 매개변수 제한

• vector A, B 크기 : 1 ~ 100,00
• vector A 값 범위 : 0 ~ 1,000,000,000
• vector B 값 범위 : 0 ~ 1
• vector A에 중복값 없음

 

3. 예제 분석

• upstream(0) 물고기는 downstream(1) 물고기를 안만날수도 있다. → A[0] 경우
• upstream(0) 물고기가 downstream(1) 물고기를 만났다면, 현재 만남에서 그치지 않고, downstream(1) 물고기를 줄줄이 만나게 된다. →  A[5]는 { A[3], A[2], A[1] }을 연속해서 만남
• 바로 위 A[5]의 경우를 보면 downstream(1) 물고기는 stack 형태로 관리되어야 한다.
• upstream(0) 물고기가 더이상 만날 물기가 없으면(downstream is empty), 해당 물고기는 살아남는다.

 

4. 코드 (C++)

#include <stack>

int solution(vector<int> &A, vector<int> &B) {

    stack<int> downstream = {}; //downstream fish 관리 stack

    int cnt = 0; //살아남은 upstream fish 수
    for(size_t i = 0; i < A.size(); i++)
    {
        if(B[i] == 1)
        {
            downstream.push(A[i]);
            continue;
        }

        //여기부터는 upstream fish 관련 코드
        bool alive = true; //upstream fish 살았는지, 죽었는지 나타내는 변수
        if(!downstream.empty()) //만날 downstream fish가 있다
        {
             //downstream fish가 다 죽거나, 
             //upstream fish가 죽을 때까지 확인한다.
            do
            {
                int fish = downstream.top();
                if(fish < A[i]) //downstream fish 죽음
                {
                    downstream.pop();
                }
                else //upstream fish 죽음
                {
                    alive = false;
                    break;
                }
            }while(!downstream.empty());
        }

        if(alive) cnt++; //upstream fish 살았다
    }

    return cnt + downstream.size();
}