[Javascript] Codility Lesson 7 - Fish

 

문제: https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

 

문제 요약: 

• 함수 인자로 A, B 배열이 주어진다. (A와 B의 길이는 동일)
• 배열 A 요소는 물고기의 크기를 나타내며 범위는 0 ~ 1,000,000,000이다. 숫자가 클수록 큰 물고기이다.
• 배열 B 요소는 0, 1로 이루어져 있고 물고기의 방향을 나타낸다. 0은 상류, 1은 하류로 움직이는 것을 의미한다. 
• 큰 물고기가 작은 물고기를 잡아먹는다.
• 최종까지 살아남는 물고기의 수를 구하여 반환한다.

 

시도 1

function solution(A, B) {
    // 모두 같은 방향으로 움직인다면 모든 물고기가 살 수 있다.
    if (B.indexOf(0) === -1 || B.indexOf(1) === -1) {
        return B.length;
    };

    let count = 0;
    // a.하류로 움직이는 물고기 중 가장 위에 있는 물고기의 위치 
    let firstDownstream = B.indexOf(1);
    // b.상류로 움직이는 물고기 중 가장 아래에 있는 물고기의 위치
    let lastUpStream = B.lastIndexOf(0);
    
    // a보다 상류에 있는 물고기는 마주치는 물고기 없이 헤엄칠 수 있고
    // b보다 하류에 있는 물고기 역시 마주치는 물고기 없이 헤엄칠 수 있다.
    count = firstDownstream + (B.length - 1 - lastUpStream);

    // 순회할필요 없는 부분 자르기
    A = A.slice(firstDownstream, lastUpStream + 1);
    B = B.slice(firstDownstream, lastUpStream + 1);

    let uStack = [];
    let dStack = [];

    for (let i = 0; i < B.length; i++) {
    	// 상류로 헤엄치는 물고기는 uStack, 하류로 헤엄치는 물고기는 dStack에 저장
        B[i] === 0 ? uStack.push(A[i]) : dStack.push(A[i]);

        // 양 스택에 물고기가 들어가면 크기를 비교하고, 작은 물고기는 stack에서 제거한다.
        while (uStack.length && dStack.length) {
            uStack[uStack.length - 1] > dStack[dStack.length - 1] ?
            dStack.pop() : uStack.pop();
        };
    }

    count += uStack.length + dStack.length;
    return count;
}

https://app.codility.com/

for문을 통해 순회하는 리스트의 크기를 줄이면 효율성이 올라가겠지 라는 생각으로 작성한 코드이다. for문 돌리기 전, 명확하게 '반대편에서 오는 물고기를 마주칠 일이 없는 물고기'의 위치를 구하고 해당 물고기들은 제거한 뒤, 확인이 필요한 물고기로만 구성된 리스트를 순회하였다. 하지만 이렇게 작성하니 가독성이 떨어지고 퍼포먼스도 기대한 것만큼 나오지 않았다. 또한 이 처리를 위해 slice 메서드를 2번 썼는데, 이럴 바에는 그냥 온전한 리스트를 순회하는 게 더 나을 것 같다는 생각이 든다.

 

 

시도 2

function solution(A, B) {
    if (B.indexOf(0) === -1 || B.indexOf(1) === -1) {
        return B.length;
    };

    let result = 0;
    let dStream = []; // 하류로 헤엄치는 물고기의 index 저장하는 stack

    for (let i = 0; i < A.length; i++) {
        if (B[i] === 1) {
            // 하류로 헤엄치는 물고기는 stack에 저장
            dStream.push(i);
        } else {
            while (dStream.length) {
                let dIndex = dStream.pop();
                // 하류로 헤엄치는 물고기가 더 크면 stack에 다시 넣고 while문 탈출
                if(A[i] < A[dIndex]) {
                    dStream.push(dIndex);
                    break;
                };
            };
            // 하류로 헤엄치는 물고기가 없으면 상류로 헤엄치는 물고기는 크기 상관없이 살아남음
            result = !dStream.length ? result + 1 : result;
        };
    };
    
    // 하류로 헤엄치는 물고기 중 최종까지 살아남은 물고기 수 더하기
    result += dStream.length;
    return result;
}

https://app.codility.com/

다른 분이 포스팅하신 것을 참고하여 작성했다. https://sustainable-dev.tistory.com/18 내가 작성한 것과 다른 점은 stack에 인덱스를 저장하여 1개의 stack을 사용해 해결했다는 것이다. 왜 이 생각을 못했을까 약간 현타가 왔지만 좋은 아이디어 배웠다고 생각하자!🏃‍♂️