Codility Lesson 07 - Fish( JAVA )

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

Fish coding task - Learn to Code - Codility

 

문제

- A, B배열은 N개의 정수로 이루어진 비어있지 않은 배열들이다.

- A, B배열은 게걸스러운 물고기들을 나타내며, 하류를 따라서 정렬되어 있다.

- 물고기의 번호는 0 ~ N-1( 배열 인덱스로 생각 )

- P<Q일 때, P번호의 물고기는 Q의 물고기보다 초기에 상류에 위치해 있다. 그리고 각 물고기들은 고유의 위치에 있다.( 겹쳐지지 않는다 )

- P번째 물고기의 A[P]는 물고기의 크기, B[P]는 물고기의 방향을 나타낸다( 0: upstream(상류) 방향 / 1: downstream(하류) 방향 )

- 서로 다른방향으로 향하는 물고기들 끼리 마주쳤을 땐, 큰 쪽의 물고기가 작은 쪽의 물고기를 잡아먹는다.

  상세히 얘기하자면, P<Q에서 B[P]=1( 하류로 흐름 ), B[Q]=0( 상류로 흐름 )일 때,

  A[P]>A[Q] : P가 Q를 먹고, 계속 하류방향으로 흐른다.

  A[Q]>A[P] : Q가 P를 먹고, 계속 상류방향으로 흐른다.

- 물고기들의 모든 흐름 속도는 동일하다. 즉 같은 방향으로 흐르는 물고기들은 절대 마주칠 일이 없다.

- 목표 : 얼마나 많은 물고기들이 살아남을지를 구하라( 살아 남은 물고기들의 수를 return )

- 예시 : A[0] = 4 B[0] = 0 A[1] = 3 B[1] = 1 A[2] = 2 B[2] = 0 A[3] = 1 B[3] = 0 A[4] = 5 B[4] = 0

   이 예시에서 1번 물고기는 2,3번 물고기를 만나서 잡아먹고, 마지막으로 4번 물고기에게 잡아먹혀 0, 4번 물고기 2마리만 살아남게 된다.

 

제한조건

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [0..1,000,000,000];
• each element of array B is an integer that can have one of the following values: 0, 1;
• the elements of A are all distinct.

N은 1 ~ 100,000 사이의 정수이다.

A 배열의 원소는 0 ~ 1,000,000,000 사이의 정수이다.

B 배열의 원소는 0 or 1만 존재한다.

A 배열의 원소들은 모두 구분된다( 중복이 없다 )

 

풀이

- stack 자료구조를 활용하여, stack에는 downstream으로 향하는 물고기( 크기)만을 쌓는다.

- LIFO( Last In First Out )의 구조를 활용

- for문을 A or B 배열만큼 순회하며 downstream으로 가는 물고기는 stack에 쌓고, upstream으로 가는 물고기를 만날 때는 stack에 쌓여있는지를 확인 -> 없으면 count를 올리고, 있으면 크기를 확인한다.

- 크기를 확인하여 stack에서 꺼낸 것이 더 크면 stack에 다시 쌓고, 작으면 그다음 stack에 쌓인 것을 꺼낸다.

- 위의 분기를 반복하여 stack의 사이즈가 0이 된다면 count를 올린다.

- for문을 모두 순회 후 stack의 size를 확인하여 size가 0이면 count가 살아있는 물고기, stack의 size가 0이 아니면 count + stack.size()가 살아있는 물고기의 수이다.

 

예상 시간복잡도 : O(N) - for문 만큼 순회

 

소스코드

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A, int[] B) {
        // write your code in Java SE 8

        Stack<Integer> stack = new Stack<>();
        int count = 0;
        int N = A.length;

        for( int i=0; i<N; i++ ){
            if( B[i] == 0 ){    // to upstream
                if( stack.size() == 0 ) count++;
                else{
                    while( stack.size() != 0 ){
                        int tmpSize = stack.pop();
                        if( A[i] < tmpSize ){
                            stack.push(tmpSize);
                            break;
                        }
                    }
                    if( stack.size() == 0 ) count++;    // 상류로 향하는 물고기가 저장되어 있던 하류로 가는 물고기의 크기보다 클 때
                }
            }else{
                stack.push(A[i]);
            }
        }

        return count + stack.size();
    }
}