[Codility] Lesson 7: Stacks and Queues - Fish (javascript) 문제 풀이

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

Fish coding task - Learn to Code - Codility

- N 개의 정수로 구성된 두 개의 비어있지 않은 배열 A와 B가 제공
- 배열 A와 B는 강의 흐름을 따라 상류->하류로 정렬된 강에 존재하는 N 개의 물고기를 나타냄
- 배열 A는 물고기의 크기를 나타냄
- 배열 B는 물고기의 이동 방향을 나타냄. 0: 상류로 흐르는 물고기, 1: 하류로 흐르는 물고기
- 두 물고기가 반대 방향으로 움직이로 그들 사이에 다른 (살아있는) 물고기가 없으면 결국 서로 만나게 됨
- 두 물고기가 만나면 크기가 더 큰 물고기만 살아남을 수 있음
- 모든 물고기는 같은 속도로 흐르고 있다고 가정
  => 같은 방향으로 움직이는 물고기는 절대 만나지 않음
- 살아남을 물고기 수를 return
- 가장 효율적인 알고리즘 작성
- 배열 A의 각 요소는 [0..1,000,000,000] 범위 내의 정수이며, 모두 다른 값을 가짐
- 배열 B의 각 요소는 0 또는 1 중 하나

 

Solution

CASE 1: 살아있는 물고기를 스택에 저장해 비교 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    const alive = [];
    
    alive.push(0);
    let i = 1;
    while(i < N){
        if(B[i] == 0 && B[alive[alive.length-1]] == 1){
            if(A[i] > A[alive[alive.length-1]]){
                alive.pop();
            }
            else{
                i++;
            }
        }
        else{
            alive.push(i);
            i++;
        }
    }
    
    return alive.length;
}

- N : 배열 A의 길이
- alive : 살아있는 물고기를 저장할 스택
- 0번째 물고기를 alive 스택에 push
- i가 1부터 N까지 while문을 돌며 만나는지 확인
    두 물고기가 만나게 되면, 크기를 비교해 크기가 작은 물고기를 alive 스택에서 제거(pop)하거나 alive 스택에 추가(push)하지 않고 넘어간다
    두 물고기가 만나지 않는 경우, alive 스택에 i번째 물고기를 추가한다
- while문이 모두 종료되면 alive 스택의 길이를 return

 

CASE 1: Result

app.codility.com/demo/results/trainingRQBDND-BHN/

 

CASE 1: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

결론

두 물고기가 만나게 되는 경우를 찾으면 다음과 같다.

따라서, i번째 물고기의 이동 방향이 0이면서, alive 스택의 top에 위치한 물고기의 이동 방향이 1인 경우를 찾으면 된다.