-
fishStudy/알고리즘 2018. 1. 19. 09:24
==============================================================================
N개의 정수로 구성된 배열 A와 B가 주어진다. 배열 A와 B는 강의 흐름에 따라 순서가 매겨진,
강 안의 게걸스러운 물고기 N마리를 나타낸다.
물고기는 0부터 N-1 까지로 숫자가 매겨져 있다. 만약 P < Q인 두 물고기가 있다면,
물고기 P는 물고기 Q보다 초기에 상류에 있다. 초기에 각 물고기는 유일한 위치를 가진다.
물고기 P는 A[P]와 B[P]로 표현된다. 배열 A는 물고기의 크기를 포함한다. 모든 요소는 유일하다.
배열 B는 물고기의 방향을 포함한다. 오직 0 또는 1만 포함한다.
- 0은 물고기가 상류로 흐르고 있음을 나타내고,
- 1은 물고기가 하류로 흐르고 있음을 나타낸다.
만약 두 물고기가 반대되는 방향으로 움직이고 그 사이에 (살아있는) 다른 물고기가 없다면,
그들은 결국 서로 만나게 된다. 그렇게 되면 오직 한 물고기만 살아남을 수 있다
- 더 큰 물고기가 작은 물고기를 먹는다. 더 정확하게는 P < Q, B[P] = 1, B[Q] = 0 이고
그사이에 살아있는 물고기가 없는 물고기 P와 Q가 서로 만나게 되면 그들이 만난 이후에는
- 만약 A[P] > A[Q]이면 P가 Q를 먹고 P는 계속 하류로 흐르고,
- 만약 A[P] < A[Q]이면 Q가 P를 먹고 Q는 계속 상류로 흐른다.
모든 물고기는 같은 속도로 흐른다고 가정한다. 물고기가 같은 방향으로 움직인다면
절대 만나지 않는다는 것이다. 목표는 살아남은 물고기의 숫자를 구하는 것이다.
예를 들어, 배열 A와 B가 다음과 같다고 생각하면:
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을 제외한 모든 물고기가 상류로 움직인다.
물고기 1은 물고기 2를 만나고 먹는다. 그리고 물고기 3을 만나서 역시 먹는다.
마지막으로 물고기 4를 만나서 먹힌다. 남은 두 물고기 0과 4는 절대 만나지 않고 영원히 살아남는다.
함수 작성
class Solution { public int solution(int[] A, int[] B); }
N개의 정수로 구성된 배열 A와 B가 주어지고, 살아남은 물고기의 숫자를 리턴한다.
예를 들어, 위에 본 배열들이 주어진다면, 위에서 설명한 것처럼 함수는 2를 리턴해야한다.
가정:
- N은 [1..100,000] 범위의 정수;
- 배열 A의 요소는 [0..1,000,000,000] 범위의 정수;
- 배열 B의 요소는 다음 값 중 하나를 가질 수 있다: 0, 1;
- 배열 A의 요소는 모두 다르다.
복잡도:
- 최악의 시간복잡도는 O(N);
- 최악의 공간복잡도는 O(N), 입력 공간 제외
배열의 요소는 수정될 수 있다.
==============================================================================
https://app.codility.com/demo/results/training5WYY2X-R4A/25점...
아 어려워 -_- 이게 왜 Easy 야...
생각의 벽을 깨지 못하는중.. 남이 해놓은거 보면 또 확 와닿겠지. 그건 내께 아닌디..
'Study > 알고리즘' 카테고리의 다른 글
Brackets (0) 2018.01.18 NumberOfDiscIntersections (0) 2018.01.16 MaxProductOfThree (0) 2018.01.16 Distinct (0) 2018.01.15 Triangle (0) 2018.01.15 MinAvgTwoSlice (0) 2018.01.15 GenomicRangeQuery (0) 2018.01.15 PassingCars (0) 2018.01.12 CountDiv (0) 2018.01.12 MaxCounters (0) 2018.01.12