[Codility] Lesson 7 : Fish - JAVA

문제

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:
 
        class Solution { public int solution(int[] A, 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.

Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A, int[] B)에 입력되는 배열 A와 B의 길이(N)는 1 ~ 100,000까지 이고,
배열 A에 저장되는 요소는 0 ~ 1,000,000,000이며,
배열 B에는 0 또는 1만 저장된다.
또한 배열 A에 저장된 요소의 값은 모두 다르다.

배열 A는 물고기의 크기, 배열 B는 물고기가 움직이는 방향을 나타낸다.
배열 B의 값이 0인 경우 물고기는 상류로 올라가며,
배열 B의 값이 1인 경우 물고기는 하류로 내려간다.

예를 들어 배열 A와 B가 다음과 같은 경우

        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

A[1] 물고기는 하류로 이동한다.
이 때 A[1]이 A[2]보다 크므로 A[2] 물고기는 A[1]에게 잡아먹힌다.
그리고 다시 A[1]과 A[3]비교한다.
A[1]이 A[3]보다 크므로 A[3] 물고기는 A[1]에게 잡아먹힌다.
마지막으로 A[1]은 A[4]보다 작으므로 A[4]물고기에게 A[1] 물고기가 잡아먹힌다.

이러한 반복 작업을 수행한 후 최종적으로 살아남은 물고기의 수를 찾아 반환한다.

 

풀이 - 1

import java.util.Stack;
class Solution {
    public int solution(int[] A, int[] B) {
        Stack<Integer> fishStack = new Stack<Integer>();
        int count = 0;
        for(int i=0; i<A.length; i++) {
            if(B[i] == 1) {
                fishStack.push(A[i]);
            } else {
                while(!fishStack.isEmpty()) {
                    int peekSize = fishStack.peek();
                    if(peekSize > A[i]) break;
                    else fishStack.pop();
                }
                if(fishStack.isEmpty()) count++;
            }
        }
        return count + fishStack.size();
    }
}

 

'풀이 - 1'에 대한 회고

 

이번에도 다른 사람의 문제 풀이 방식을 참고!

B의 값이 1인, 즉 하류로 이동하는 물고기가 나타나는 경우만 stack에 저장한다.

그리고 하류로 이동하는 물고기와 상류로 이동하는 물고기의 크기를 비교한다.

상류로 이동하는 물고기의 크기가 더 크고 하류로 이동하려는 물고기의 데이터가 Stack에 없는 경우

생존한 물고기의 수를 1 증가시켜준다.

 

 

그 결과 정확도, 퍼포먼스가 모두 100%.

 

 

시간복잡도도 O(n)이다.

 

이번 stack문제를 2개 풀면서 다른 사람이 작성한 코드를 안 본 경우가 없다.

아직 경험이 많이 부족하다는 증거!

그러니 꾸준히 코딩테스트 연습을 해야겠다.