코딩테스트 연습 - 롤케이크 자르기

문제 풀이 아이디어

시간 복잡도

롤케이크의 최대 길이는 1,000,000입니다. 즉 이중반복문을 사용하면 안되고 무조건 O(N)의 알고리즘으로 답을 구해야 합니다.

또한 케이크를 자르는 것에 착안해서 Array의 subscript를 사용해서 직접 자르는(!) 방법도 지향해야 합니다. Swift는 Array를 직접 조작하는데 비용이 많이 듭니다.

Set

철수와 동생이 케이크를 나누는데 있어서 중요한 것은 토핑의 총량이 아니라 토핑의 종류입니다. 따라서 특정 토핑의 갯수는 전혀 중요하지 않고 중요한 것은 자른 조각에 토핑이 몇 “종류”나 포함되어 있느냐 입니다. 따라서 중복된 토핑의 종류만 셀 수 있도록 Set을 사용하도록 하겠습니다. Set의 insert와 count는 O(1)입니다.

철수와 동생 그리고 확인: 3개의 반복문

주어진 롤케이크를 1번만 순회해서, 즉 하나의 반복문으로 철수와 동생이 먹는 토핑의 종류를 반복문 안에서 복잡한 연산을 수행해야 합니다. 저는 O(N)의 반복문 3개를 사용해서 즉 O(3N)의 알고리즘으로 풀었습니다. 자세한 설명은 아래 코드를 참고해주세요. (Big-O에서 O(3N)은 결국 O(N)입니다.)

코드

func solution(_ topping:[Int]) -> Int {
    
    // 철수가 0 ~ i까지 케이크에서 먹은 토핑의 종류
    var bro1 = Array(repeating: 0, count: topping.count)
    var set1 = Set<Int>()
    
    // 동생이 (i - 1) ~ i까지 케이크에서 먹은 토핑의 종류
    var bro2 = Array(repeating: 0, count: topping.count)
    var set2 = Set<Int>()
    
    // 철수가 먹은 토핑의 종류 구하기
    for i in 0..<topping.count {
        set1.insert(topping[i]) //👉 철수가 지금까지 먹은 토핑의 종류
        bro1[i] = set1.count
    }
    
    // 동생이 먹은 토핑의 종류 구하기
    for i in stride(from: topping.count - 1, to: -1, by: -1) {
        set2.insert(topping[i]) //👉 동생이 지금까지 먹은 토핑의 종류
        bro2[i] = set2.count
    }
    
    var ans = 0
    
    // 철수가 0 ~ i까지의 케이크를 먹었다면 동생은 i + 1 ~ topping.count - 1의 케이크를 먹는다
        // 두 구간을 비교해서 토핑의 갯수가 동일하다면 공평하게 자를 경우
    for i in 0..<(topping.count - 1) {
        if bro1[i] == bro2[i + 1] { ans += 1 }
    }
    
    return ans
}