[Codility(코딜리티)] Lesson7. Fish (100%)

Lesson 7 Stacks and Queues - Fish (Java Solution)

app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

Fish coding task - Learn to Code - Codility

---

문제

두 개의 배열 A, B가 주어진다

두 배열의 길이는 같다

A는 물고기가 가진 번호이고, 이 값은 distinct 하다

B는 물고기가 움직이는 방향이다 (0이면 <-, 1이면 ->)

여기서 다른 방향으로 움직이는 물고기가 만나면 숫자가 더 큰 물고기가 살아남는다

결국 총 살아남은 물고기의 개수를 출력하는 것이다

 

예를 들어서 설명하면,

A = {4,3,2,1,5}

B = {0,1,0,0,0}

여기서 0번 인덱스 물고기 방향은 0으로 <-로 간다. 즉, 더 이상 만날 수 있는 물고기가 없다

다음 1번 인덱스 물고기는 1로 ->로 간다. 2번 인덱스 물고기는 0으로 <- 로 간다

1번 인덱스 물고기가 숫자가 더 커서 살아남는다 

이렇게 반복하다 보면 결국 0번, 4번 물고기기만 살아남게 된다

해결

이번 문제는 스택을 이용해서 풀었다

배열 A를 사이즈만큼 돌린다 

A[0] ~ A[N-1]까지 값을 꺼내면서,

그리고 그 값의 방향이 1이면 스택에 넣고,

0이면, 스택이 비어있는지 체크한다

스택이 비어있다면 fish_0_cnt을 하나 올리고,

비어있지 않으면 하나씩 꺼내서 값과 비교한다

스택에서 꺼낸 값이 더 크다면 break 하고 다음 단계로 진행한다

결국 서로 방향이 반대인 것들은 모두 계산되고, 

0인 것들의 개수는 fish_0_cnt,

1인 것들은 fish_1_stack에 남게 된다

cnt + fish_1_stack.size()를 출력하면 남은 물고기의 개수이다

public class Fish {

    public int solution(int[] A, int[] B) {
        Stack<Integer> fish_1_stack = new Stack<>();
        int fish_0_cnt = 0;

        for (int i=0; i<A.length; i++) {
            int fishNum = A[i];
            if (B[i] == 1) {
                fish_1_stack.push(fishNum);
            } else {
                if (fish_1_stack.empty()) {
                    fish_0_cnt++;
                } else {
                    int size = fish_1_stack.size();
                    for (int j=0; j<size; j++) {
                        int pop = fish_1_stack.pop();
                        if (fishNum < pop) {
                            fish_1_stack.push(pop);
                            break;
                        }
                    }
                    if (fish_1_stack.size() == 0) fish_0_cnt++;
                }
            }
        }

        return fish_0_cnt + fish_1_stack.size();
    }
 }