codility - Fish 정답 및 해설

난이도 ★★★☆☆

문제를 보시려면 여기를 클릭

문제 요약

최종적으로 몇 마리의 물고기가 살아남는지 리턴하기  1. A.length 가 물고기의 숫자이다.  2. index 가 각 물고기 번호인데, index 가 작을수록 강의 상류에 있다.  3. A[index] 는 각 물고기의 크기이며, 큰 녀석이 작은 녀석을 만나면 잡아먹는다.  4. B[index] 는 각 물고기의 방향이며, 0 은 상류로 가는 방향, 1 은 하류로 가는 방향이다.  5. 모든 물고기의 속도는 같다. (즉, 같은 방향끼리는 못 만난다)

힌트

Stack 을 써야한다. 왜 써야하는지 깨달으면 절반 이상은 푼 것이다.  (B[index] == 1 인 녀석들을 Stack 에 넣자)

이하는 코드입니다.

public int solution(int[] A, int[] B) {
    int aliveCount = 0;
    Stack<Integer> downFishes = new Stack<>();
    
    for (int i = 0; i < A.length; i++) {
        if (B[i] == 0) {    // up fish
            aliveCount++;
            
            if (downFishes.isEmpty()) {
                continue;
            }
            
            int downFish = downFishes.peek();
            
            while (true) {
                aliveCount--;
                
                if (A[downFish] < A[i]) {
                    downFishes.pop();
                    
                    if (downFishes.isEmpty()) {
                        break;
                    }
                    
                    downFish = downFishes.peek();
                }
                else {
                    break;
                }
            }
        }
        else {    // down fish
            downFishes.add(i);
            aliveCount++;
        }
    }
    
    return aliveCount;
}