Codility Lesson7 - Fish

🔍 문제

---

 

Fish coding task - Learn to Code - Codility

강 한 줄기가 있다고 했을 때, 물고기들의 사이즈가 담긴 A 배열과 물고기들이 향하는 방향을 알려주는 배열 B가 주어진다. 만약, 위로 향하는 물고기와 아래로 향하는 물고기가 만나게 되면, 사이즈가 더 작은 물고기는 더 큰 물고기에게 잡아먹히게 된다. 이렇게 해서 최종 살아남게 되는 물고기 수를 구하면 된다.

 

✏️ 풀이 - JS

---

물고기가 만나게 되는 경우는 오직 아래로 향하는 물고기 + 위로 향하는 물고기의 조합 밖에 없다. 따라서 B배열의 값이 (1, 0)이 되는 인덱스의 물고기 두 마리가 만나게 된다.
B배열을 순회하면서 값이 1인 물고기(아래로 향하는 물고기)의 인덱스는 downFish.push()로 차례대로 넣어준다. B배열 값이 0인 물고기(위로 향하는 물고기는) 그 전에 아래로 내려오는 물고기가 없다면, 이 물고기는 무조건 살아남는다고 할 수 있다. 반대로 내려오는 물고기가 있다면 내려오는 물고기들과 모두 싸워야한다. 내려오는 물고기들이 전부 먹히고 올라가는 물고기가 승리한다면 이 물고기는 결국 살아남을 수 있다. 현재 올라가는 물고기가 내려오는 물고기한테 먹힌다면 내려오는 물고기는 살아남아서 계속 내려와야 하므로 downFish.push()로 다시 넣어준다.

 

시간복잡도는 O(N), correctness, performance 모두 100%가 나왔다.

function solution(A, B) {
    let downFish = [];
    let survivedFishCnt = 0;

    for(let i = 0; i < A.length; i++) {
        if(B[i] === 1) {
            downFish.push(i);
        } else {
            while(downFish.length !== 0) {
                const downFishIdx = downFish.pop();
                if(A[downFishIdx] > A[i]) { //올라가는 물고기가 진 경우
                    downFish.push(downFishIdx);
                    break;
                }
            }

            if(downFish.length === 0) survivedFishCnt++; //내려오는 물고기가 없는 경우
        }
    }

    survivedFishCnt += downFish.length;

    return survivedFishCnt;
}