Codility 문풀 - Fish

Codility 문제 - Fish

살아 남은 물고기의 수를 반환

 

■ 문제 풀이

1) 문풀 설명
- 배열 A는 물고기의 사이즈, 배열 B는 물고기의 방향을 나타냄
- 배열 A의 요소는 unique
- 배열 B는 0 또는 1의 값만을 가짐, 배열 B의 요소 0은 상류/ 배열 B의 요소 1은 하류
- 물고기 P는 A[P] 와 B[P]를 나타냄, 물고기 Q는 A[Q]와 B[Q]
- P<Q, B[P] = 1이고 B[Q] = 0인 경우, 두 물고기는 만나게 된다.
- 만약 A[P]>A[Q] 경우, 물고기 P는 물고기 Q를 eat, 그리고 downstream
- 만약 A[P]<A[Q] 경우, 물고기 Q는 물고기 P를 eat, 그리고 upstream
- 같은 방향으로 움직이는 물고기는 만나지 않는다. 

2) 예제
배열 A와 배열 B가 있다.
Array A = {4, 3, 2, 1, 5}
Array B = {0, 1, 0, 0, 0}
N=1 경우의 물고기를 제외하곤 모두 상류
A[1] > A[2]인 경우 N=2인 물고기 eat
A[1] > A[3]인 경우 N=3인 물고기 eat
A[1] < A[4]인 경우 N=1인 물고기 eat
N이 0, 4인 경우의 물고기가 살아남게 됨으로 2를 반환

3) 힌트
- Stack을 활용
- B 배열에서 B[i] = 0(상류 방향), B[i+1] = 1(하류 방향) 순인 경우에는 두 마리의 물고기가 만나지 않음
- 하지만,  B[i] = 1(하류 방향), B[i+1] = 0(상류 방향) 순인 경우에는 두 마리의 물고기가 만나게 된다. 

 

package soyeon.study.codility;

import java.util.Stack;

public class Fish {

    public static int solution(int[] A, int[] B) {
        int aliveFish = 0;
        Stack<Integer> downFish = new Stack<>();

        for(int i=0; i<A.length; i++){
            if(B[i] == 0){
                if(downFish.isEmpty()){
                    aliveFish++;
                }else {
                    while(downFish.size()>0){
                       if(A[i] > downFish.peek()){
                            downFish.pop();
                        }else{
                           break;
                       }
                    }
                    if(downFish.isEmpty())
                        aliveFish++;
                }
            }else{
                downFish.push(A[i]);
            }
        }

        aliveFish += downFish.size();
        return aliveFish;
    }

    public static void main(String[] args) {
        //TEST Data
        int[] A = {4, 9, 2, 1, 5, 6, 7};
        int[] B = {0, 1 , 1, 1, 0, 0, 1};
        
        System.out.println("alive fish : " + solution(A, B));	//return 3
    }
}