[Swift 알고리즘] Codility lesson5 - PassingCar

안녕하세요 코코종입니다! 이번에는 lesson 5 - Prefix sum으로 넘어왔습니당

이 문제는 대체.... 설명이 너무 이해가 안가서 오래걸린 문제입니다 ㅠㅠㅠ

 

간단 설명 갑니다. 0 은 >, 1은 < 라고 했을때 문제의 예시에서 나오는 경우에 > < > > < 가 되는데요

이때 0번의 차는 자기랑 마주오는 3대의 차를 만납니다(1, 3, 4), 또 2번의 차는 3,4 번의 마주오는 차를 만나게 되면서 총 5번을 만난다! 이말입니다.

실제로 문제를... 한 3번 읽어도 뭔소린가해서(index라는 식으로 표현해둬서 저는 그 자리에 차가 있다는줄 알았네요) 다른 블로그 글을 참고해서 이해했습니다.

 

먼저 처음에 틀린 방법입니다(사실 시간 초과일거 알고 있었지만..!) 말그대로 0을 만날때 그보다 뒤에 있는 index에 1을 세어서 더해주는 방법이었습니다. (그와중에 lesson 주제 지킨다고 suffix 사용함ㅋㅋㅋ)

이 방법은 for문에서 A에 계속 접근하다보니까 시간이 오래걸릴수 밖에 없었죠.. 답만 맞았고 시간복잡도에서 O(N**2) 으로 틀렸습니당.

import Foundation
import Glibc

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

public func solution(_ A : inout [Int]) -> Int {
    // P: 0 -> east, Q: 1 -> west
    var result = 0
    // 아이디어 1. a==0 인 기준에서 오른쪽에 있는 1의 갯수를 모두 더한다.
    for i in 0..<A.count {
        var smallSum = 0
        if A[i] == 0 {
            let suff = Array(A.suffix(from: i+1))
            smallSum = suff.reduce(0,+)
        }
        result += smallSum
        if result >= 1000000000 {
            return -1
        }
    }

    return result
}

 

그래서 바아로~~ 어떻게 하면 A를 여러번 거치지 않고 해결할까 했는데 바로 dp에서 처럼 그 위치에서 오른쪽에 있는 수를 매번 돌면서 계산하지 않고 몇인지 저장했다가 1(< 방향)을 만나면 빼주는 식으로 했습니다.

import Foundation
import Glibc

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

public func solution(_ A : inout [Int]) -> Int {
    // P: 0 -> east, Q: 1 -> west
    var total = A.reduce(0,+)
    var result = 0
    // 아이디어 2. 기존의 아이디어를 가져가며 전체의 합인 sum을 저장해서 써먹기
    for i in 0..<A.count {
        if A[i] == 0 {
            result += total
        } else if A[i] == 1 {
            total -= 1
        }

        if result > 1000000000 {
            return -1
        }
    }

    return result
}​

 

시간 복잡도 O(N)으로 깔~끔하게 통과를 했습니다 쿠쿠...

문제 이해하는데 더~~~ 오래 걸려버린 이번 문제였습니다.