Codility Java Fish

업데이트:

문제

Link

코드

// 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");

import java.util.Stack;

class Solution {
  public int solution(int[] A, int[] B) {
    Stack<Integer> stack = new Stack<>();
    int lastSize = 0;
    int aliveCount = 0;
    for (int idx = 0; idx < A.length; idx++) {
      if (B[idx] == 1) {
        stack.add(A[idx]);
      } else {
        // Check to fish size.
        while (!stack.isEmpty()) {
          lastSize = stack.peek();
          if (lastSize < A[idx]) {
            stack.pop();
          } else {
            break;
          }
        }
        if (stack.isEmpty()) {
          aliveCount++;
        }
      }
    }
    return aliveCount + stack.size();
  }
}

설명

  1. 물고기의 크기를 임시 저장하기 위한 저장소로 Stack을 사용한다.
  2. 주어진 배열 A를 반복하고 B를 참조하여 살아있는 물고기의 수를 계산한다.
    • 하류로 흘러가는 물고기일 경우 변수 stack에 물고기의 크기를 저장한다.
    • 상류로 흘러가는 물고기일 경우 변수 stack에 있는 물고기의 크기 중 해당 물고기의 크기보다 작을 경우 변수 stack에서 제외하고, 살아있는 물고기 수를 저장하는 aliveCount에 추가한다.
  3. 반복이 완료되면 살아있는 물고기 수를 저장하는 aliveCount와 물고기의 크기를 임시 저장하는 stack의 크기를 합쳐서 주어진 문제의 결과로 반환한다.
    • 변수 aliveCount는 상류로 흐르는 물고기의 수이다.
    • 물고기의 크기를 임시 저장하는 stack은 반복 이후에는 생존한 하류로 흐르는 물고기의 크기이므로, stack의 크기는 생존한 하류로 흐르는 물고기의 수이다.

결과

Link

소스

Sample Code는 여기에서 확인 가능합니다.

댓글남기기