[프로그래머스] 롤케이크 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/132265

잡담
최근 코딩테스트를 2번 참가하였는데 모두 C++로 봐야해서 오랜만에 문법 공부를 했는데 나름 기억이 새록새록 났다.
코딩테스트가 C++과 Swift 모두 지원해준다면 다익스트라, 플로이드 등 문제가 나왔을 때는 C++로 풀고 그 외 문제는 Swift로 풀어야겠다는 생각을 하였다.

✍️ 첫번째 접근

롤케이크를 잘랐을 때 나오는 두 개의 롤케이크가 같은 토핑 종류의 수가 나오게끔 자르면 된다.
철수의 롤케이크에 대한 정보를 갖고 있는 배열 arr1과 동생의 롤케이크에 대한 정보를 갖고 있는 배열 arr2를 선언했다.
롤케이크를 자를 수 있는 인덱스를 돌면서 arr1과 arr2의 토핑의 종류의 수가 같은지 판단하였는데 시간 초과가 발생하였다.
매번 arr1, arr2 배열을 초기화하고 topping의 길이가 최대 1,000,000이기 때문에 2중 for문으로 인해 발생한 것이라고 판단하였다.

import Foundation

func solution(_ topping:[Int]) -> Int {
    var answer = 0
    let maxValue = topping.max()!   // 배열의 최대 크기를 지정하기 위해
    var arr1 = Array(repeating: 0, count : maxValue+1)
    var arr2 = Array(repeating: 0, count : maxValue+1)
    for i in 0..<topping.count-1 {
        arr1 = Array(repeating: 0, count : maxValue+1)
        arr2 = Array(repeating: 0, count : maxValue+1)
        for j in 0...i {
            arr1[topping[j]] += 1
        }
        for j in i+1..<topping.count {
            arr2[topping[j]] += 1
        }
        if arr1.filter{$0 == 0}.count == arr2.filter{$0 == 0}.count {
            answer += 1
        }        
    }
    
    return answer
}

✍️ 두번째 접근

Array로 선언하지 않고 Set으로 선언하여 접근했다. 하지만, 이번에도 시간 초과가 발생하였다.
for문은 비록 한개를 사용하였지만, 그 안에서 Array를 Set으로 계속해서 형변환하였고 매번 인덱스가 증가할 때마다 새로 구하기 때문에 발생한 것이라고 판단하였다.

import Foundation

func solution(_ topping:[Int]) -> Int {
    var answer = 0
    for i in 0..<topping.count-1 {
        var s1: Set<Int> = []
        var s2: Set<Int> = []
        s1 = Set(topping[0...i])
        s2 = Set(topping[i+1..<topping.count])
        if s1.count == s2.count {
            answer += 1
        }
    }
    
    return answer
}

✍️ 세번째 접근

철수는 빈 Set인 s1에서 시작하고 동생은 모든 토핑에 대한 Set인 s2에서 시작한다.
롤케이크를 자를 수 있는 인덱스에 대한 for문을 돌기 전에 미리 각 토핑이 몇개 있는지에 대한 idxArr 배열을 선언하였다.
이제 롤케이크를 자를 수 있는 인덱스를 돌면서 s1에 토핑을 하나씩 추가하고, s2에는 idxArr 배열과 비교하여 해당 토핑이 idxArr 배열 값에 0보다 작거나 같다면 s2에서 해당 토핑을 삭제한다.
s1의 크기와 s2의 크기가 같으면 answer를 하나씩 증가하여 문제를 해결하였다.

import Foundation

func solution(_ topping:[Int]) -> Int {
    if topping.count == 1 {
        return 0
    }
    var answer = 0
    var s1: Set<Int> = []   // 철수
    var s2: Set<Int> = Set(topping)   // 동생
    let maxValue = topping.max()!   // 배열의 최대 크기를 지정하기 위해
    var idxArr = Array(repeating: 0, count: maxValue+5)
    for i in 0..<topping.count {
        idxArr[topping[i]] += 1
    }
    for i in 0..<topping.count-1 {
        s1.insert(topping[i])   // 철수는 토핑 하나 증가        
        idxArr[topping[i]] -= 1 // 해당 토핑의 개수 하나 감소
        if idxArr[topping[i]] <= 0 {	// 해당 토핑의 개수가 0 이하이면, s2에는 해당 토핑이 존재하면 안된다.
            s2.remove(topping[i])	// 동생은 토핑 하나 감소
        }
        if s1.count == s2.count {    // 토핑의 가짓수가 같으면 answer 증가
            answer += 1
        }
    }
    
    return answer
}