[codility] Fish

Fish

N voracious fish are moving along a river. Calculate how many fish are alive.

Task Score

100%

Correctness

100%

Performance

100%

---

 

뭔가 귀여운데 잔인한 자연의 섭리같은 문제..

A 배열에는 물고기의 크기,

B 배열에는 물고기의 방향이 나타나있다. (0이면 올라가고, 1이면 내려가고)

배열의 인덱스가 앞일수록 물고기는 더 위에 있다.

 

결국 나보다 앞 인덱스인 물고기가 내가잡아먹어서 없는상황에서 내가 위로(0) 올라가면 사는거고,

내가 다 잡아먹어서 제일 마지막 인덱스인데 내려가면 사는거다.

 

처음에 이상하게 혼자 복잡하게생각해서 스택 두개가지고 난장판을 피우다가

0%의..처참한 점수를 받고 정신차리고 하나의 스택으로 제대로 증신차리고 풀었다.

 

내려가는애들은 스택에 담아놓고

올라가는애 생기면 걔가 올라가면서 스택에 있는 내려가는애들을 꺼내서 도장깨기한다.

그러다가 내가 맨위로 올라가면 살았다고 카운트하고,

올라가는애들이 다 사라진 후에 스택 안에 남은 내려가는애들도 다 살아남은 것이므로

마지막에 다 합쳐 결과를 반환하면 된다.

 

// you can also use imports, for example:
import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        Stack<Integer> goingDownSt = new Stack<>();
        
        for (int i = 0; i < A.length; i++)  {
            int fish = A[i];
            
            if (B[i] == 0) {
                if (goingDownSt.isEmpty()) {
                    answer++; 
                } else if (goingDownSt.peek() < fish) {
                    goingDownSt.pop();
                    i--;
                }
            } else {
                goingDownSt.push(fish);
            }
        }
        
        return answer + goingDownSt.size();
    }
}