[Algorithm/Swift] Codility / Fish

문제

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

풀이

이 문제는 좀 재미있는 문제입니다.(?)

배열 A는 물고기의 크기를 배열 B는 물고기의 방향을 나타냅니다.

방향이 다른 물고기가 서로 마주할때 큰 물고기가 작은 물고기를 잡아 먹습니다.  🤜🏻  🤛🏻 🤛🏻 🤛🏻

마지막 까지 살아 남은 물고기는 몇마리인지 구합니다.

Stack를 이용하여 비교하여 답을 구해보고자 합니다.

Code O(N)

public func solution(_ A : inout [Int], _ B : inout [Int]) -> Int {
    
    var stack = Array<Int>()
    var survivor = 0

    for (index, size) in A.enumerated() {

        if B[index] == 1 {
            stack.append(size)
        } else {
        //반대 방향의 물고기를 만날일이 없는 물고기
            if stack.count == 0 {
                survivor += 1
            } else {
                
                while stack.count > 0 {
					
                    // 새로 만난 물고기(size) 사이즈가 더 크면 기존 물고기는(sizeDown) 스택에서 빼기
                    guard let sizeDown = stack.last, size > sizeDown else {
                        break
                    }

                    stack.removeLast()

                    if stack.count == 0 {
                        survivor += 1
                    }
                }
            }
        }
    }

    return survivor + stack.count

}

처음에는 재밌는 문제라고 생각했는데 좀 어려움,,

Udemy랑 다른분 소스 코드를 좀 참고했습니다...

 

역시 틀려야,,공부가 되는것 같네요..