[C++ 풀이] Codility - Lessons 7, (Stacks and Queues) Fish

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

 

문제

 

 

 

 

 

설명

 

 

배열 A[]와 B[]가 주어지고 A의 배열 요소는 물고기의 크기를 나타냅니다.

A배열의 index는 물고기의 순서를 나타내고요.

B배열은 해당 물고기가 위로 올라갈지 밑으로 내려갈지 구분해주는 요소입니다.

 

B의 배열 값은 0과 1로만 주어지며 0은 물고기가 상류로, 1은 물고기가 하류로 가는 설정입니다.

글로만 읽으면 이해가 안가실태니 그림을 첨부하겠습니다.

 

A[] = { 4, 3, 2, 1, 5}, B[] = { 0, 1, 0, 0, 0} 이라고 가정했을 때

 

이런식이 됩니다.

 

상류로 가는 물고기와 하류로 가는 물고기가 만나면 큰녀석이 잡아먹습니다.

단, 물고기의 이동속도는 동일하다고 가정해 같은 방향으로 가는 물고기들은 서로 잡아먹을 일이 없습니다.

 

즉, A[0] 녀석은 이미 선두에서 올라가고 있음으로 아무도 마주치지않고 상류로 올라가고

A[1]은 하류로 내려가기 때문에 A[2] ~ A[4] 까지 만나게 됩니다.

여기서 A[1] = 3이므로 A[2], A[3]을 잡아먹지만 A[4]에게 잡아 먹힙니다.

따라서 물고기는 총 A[0], A[4]만이 살아남음으로 2를 return하면 되는 문제입니다.

 

 

 

 

 

결과

 

 

 

// you can use includes, for example:
// #include <algorithm>
#include <stack>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A, vector<int> &B) {
    // write your code in C++14 (g++ 6.2.0)
    
    int count = 0;
    stack<int> s;
    
    for(int i = 0; i < A.size(); i++){
        if(B[i] == 1)
            s.push(A[i]);
        else{
            if(s.empty())
                count++;
            else{
                while(!s.empty()){
                    if(A[i] > s.top()){
                        s.pop();
                        if(s.empty())
                            count++;
                    }
                    else
                        break;
                }
            }
        }
    }
    
    return count + s.size();
    
}

 

 

 

https://app.codility.com/demo/results/trainingAPV6J8-ZUC/

 

 

 

처음엔 queue를 사용했는데, 계속 테스트 점수가 50점이 나오길래 생각해보고 카페에 물어보니깐 queue를 사용하면 안됐습니다.

 

역주행 하는 물고기를 나중에 만날수 록 나중에 만난 녀석들 먼저 비교해 줘야하기 때문입니다.

 

때문에 stack을 이용해야 풀 수 있는 문제입니다.