Codility Java Fish
업데이트:
문제
코드
// 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();
}
}
설명
- 물고기의 크기를 임시 저장하기 위한 저장소로 Stack을 사용한다.
- 주어진 배열 A를 반복하고 B를 참조하여 살아있는 물고기의 수를 계산한다.
- 하류로 흘러가는 물고기일 경우 변수 stack에 물고기의 크기를 저장한다.
- 상류로 흘러가는 물고기일 경우 변수 stack에 있는 물고기의 크기 중 해당 물고기의 크기보다 작을 경우 변수 stack에서 제외하고, 살아있는 물고기 수를 저장하는 aliveCount에 추가한다.
- 반복이 완료되면 살아있는 물고기 수를 저장하는 aliveCount와 물고기의 크기를 임시 저장하는 stack의 크기를 합쳐서 주어진 문제의 결과로 반환한다.
- 변수 aliveCount는 상류로 흐르는 물고기의 수이다.
- 물고기의 크기를 임시 저장하는 stack은 반복 이후에는 생존한 하류로 흐르는 물고기의 크기이므로, stack의 크기는 생존한 하류로 흐르는 물고기의 수이다.
결과
소스
Sample Code는 여기에서 확인 가능합니다.
댓글남기기