[Swift 알고리즘] Codility - PassingCars

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "Codility - PassingCars" 문제를 풀었습니다.

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

PassingCars coding task - Learn to Code - Codility

 

풀이

이번 문제는 east로 가는 이동하는 차의 index보다 큰 west로 이동하는 차의 index pair 개수를 구하라는 문제입니다.

예를 들어, east로 가는 차의 index가 [1, 3]이고 west로 가는 차의 index가 [2, 4]라면

문제에서 요구하는 pair는 (1, 2), (1, 4), (3, 4)인 것입니다. 

 

저는 east와 west를 나눠서 저장해주었습니다.

filter를 이용해도 됐지만 반복문 하나로 처리가 가능했기 때문에 그냥 반복문 안에 if 처리하여 나눴습니다.

 

두 배열 중 하나라도 비어있다면 0을 리턴해주었고,

west에서 east보다 작은 원소를 삭제해줄 것이기 때문에 reversed( ) 했습니다.

removeFirst( )가 비효율적이므로 popLast( )를 이용해야 하기 때문입니다.

 

east로 이동하는 차를 하나씩 살펴보며 현재 차의 index 보다 작은 west index는 삭제했습니다.

그럼 삭제되지 않은 나머지 원소는 자기보다 큰 값이므로 count를 구해 pairCount에 더해줍니다.

 

모든 east 차를 살펴보거나, 중간에 west가 모두 pop 됐다면 반복을 종료하고 pairCount를 return 합니다.

 

문제를 이해하는 게 더 힘들었던 이번 문제!

책을 많이 읽읍시다 

 

감사합니다!

 

전체 코드

import Foundation

public func solution(_ A : inout [Int]) -> Int {
    let maxCount = 1000000000

    //동쪽으로 이동하는 차의 index 보다 큰 서쪽으로 이동하는 차의 index
    var eastCars: [Int] = []
    var westCars: [Int] = []

    for (i, car) in A.enumerated() {
        if car == 0 {
            eastCars.append(i)
        } else {
            westCars.append(i)
        }
    }
    
    if eastCars.isEmpty || westCars.isEmpty {
        return 0
    }

    westCars = westCars.reversed() //효율적으로 원소를 제거하며 counting 하기 위해 reversed()

    var pairCount: Int = 0
    for car in eastCars {
        if pairCount > maxCount {
            return -1
        }
        
        while !westCars.isEmpty && car >= westCars.last! {
            westCars.popLast()
        }

        if westCars.isEmpty {
            break
        }
        
        pairCount += westCars.count
    }

    return pairCount
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.