[171117][Codility](C#)Fish

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

 

문제>

* N개의 정수는 N개의 물고기(A배열 : 물고기의 크기, B배열 : 물고기의 방향.)를 나타낸다.

* P(번째) < Q(번째)인 물고기라면 P물고기는 Q보다 상류에 있다.

* A배열의 모든 요소는 유일하다.

* A배열의 더 큰 물고기는 작은 물고기를 먹는다.

* B배열의 값은 0또는 1만 포함하고 0은 물고기가 상류로 1은 물고기가 하류로 향한다.

* 같은방향의 물고기 끼리는 절대 만나지 않는다.

* 살아 남은 물고기의 숫자를 구하라.

 

해결방법. *스택사용.

1) 헤엄치는 중인 물고기 번호를 체크할 Stack을 만든다.

2) 물고기 수 까지 1씩 증가하는 반복문을 돌린다.

- 내부 추가 반복문으로

조건1) stack수가 0보다 크고

조건2) B[stack의 마지막으로 들어간 물고기 번호] - B[현재 물고기번호]의 방향 차가 1이고

조건3) A[stack의 마지막으로 들어간 물고기 번호]크기 < A[현재 물고기번호]크기가 작으면

- stack의 마지막으로 들어간 물고기 번호를 제거.

- 조건이 하나라도 맞지 않을 때 까지 반복.

- stack수가 0이거나 B[stack의 마지막으로 들어간 물고기 번호] - B[현재 물고기번호]의 방향 차가 1이 아니면 물고기 번호를 추가.

 

using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;

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

class Solution
{
    public int solution(int[] A, int[] B)
    {
        Stack<int> fish = new Stack<int>();
        for (int i = 0; i < A.Length; i++)
        {
            while (fish.Count > 0
            && B[fish.Peek()] - B[i] == 1
            && A[fish.Peek()] < A[i])
            {
                fish.Pop();
            }
            if (fish.Count == 0 || B[fish.Peek()] - B[i] != 1)
            {
                fish.Push(i);
            }
        }
        return fish.Count;
    }
}

 

 

 

17.11.17.(0030)

 

회고 : 해석은 그림그리면서 삽질했는데 운좋게 빨리 풀었다.