[Swift] [22일차] 롤케이크 자르기

핀·2024년 12월 29일

programmers swift

SwiftAlgorithm

목록 보기

25/105

Programmers-롤케이크 자르기

문제 설명

1차원 배열이 길게 주어지는데,

이걸 순서 그대로두면서 두 동강내서

안에 들어간 종류의 갯수 동일하게, 되면 방법의 수, 그게 안되면 return 0

문제 접근

먼저 든 생각은 일단 종류의 갯수만하는거니까

Set쓰면 좋을 것 같다는 것
방법의 개수니까 어떻게 두동강을 내줄지, 이걸 전부다 짜르면 너무 시간이 오래걸릴 것 같은데..

import Foundation

func solution(_ topping: [Int]) -> Int {
    var answer = 0
    var LEN = topping.count
    for i in 0 ..< LEN {
        print("I \(i) 까지 , \(i + 1)부터 \(LEN - 1)")
    }
    return answer
}
solution([1, 2, 1, 3, 1, 4, 1, 2])

이렇게 프린트를 찍어보면

I 0 까지 , 1부터 7
I 1 까지 , 2부터 7
I 2 까지 , 3부터 7
I 3 까지 , 4부터 7
I 4 까지 , 5부터 7
I 5 까지 , 6부터 7
I 6 까지 , 7부터 7
I 7 까지 , 8부터 7

이런식으로 나오는데, 이렇게 짤라서 Set으로 만들고, 길이 비교하면 되지 않으려나? 싶었다.

1차 풀이

import Foundation

func solution(_ topping: [Int]) -> Int {
    var answer = 0
    var LEN = topping.count

    for i in 0 ..< LEN {
        let younger = Set(topping[0 ... i])
        let older = Set(topping[i + 1 ..< LEN])

        if younger.count == older.count {
            answer += 1
        }
    }
    return answer
}

이렇게 하니까 예제는 통과했는데, ALL 시간초과가 뜨더라 !

계속 짜르면서 Set으로 반복문 마다 생성해주는게 말이 안된다고 생각했다. 이미 있는 것에서 insert쳐주면서 하면 될 것 같기도??

2차 개선

import Foundation

func solution(_ topping: [Int]) -> Int {
    var answer = 0
    let LEN = topping.count

    var younger = Set<Int>()
    var older_dict = [Int: Int]()
    topping.forEach { older_dict[$0, default: 0] += 1 }
    var older_count = older_dict.count // 총 종류 개수

    for i in 0 ..< LEN {
        younger.insert(topping[i])
        if older_dict[topping[i]]! <= 1 {
            older_dict[topping[i]]! -= 1
            older_count -= 1
        }
        if younger.count == older_count {
            answer += 1
        }
    }
    return answer
}

set에 insert하는 동생의 케이크는 시간복잡도가 안높으니까 younger은 set
반대로 동생에게 할당하는만큼 빼줘야하는 older는 카운팅해주기 위해 딕셔너리를 채용했다.
그래서 이걸 older_count로 관리해주면서 최대한 시간이 오래걸리지않게 유도했고..

채점 결과

정확성: 25.0
합계: 25.0 / 100.0

이렇게 나오긴했는데, 시간초과 안뜬거만으로도 감사했다. 이제 좀 틀린거만 고치면 될 것 같기도 ?

아마 문제

if older_dict[topping[i]]! <= 1 {
            older_dict[topping[i]]! -= 1
            older_count -= 1
        }

아마 문제는 이 친구에서 나오는 것 같다. 1보다 작을 때도 그렇고, 1보다 클때는 차감이 안되는 것이라서 이 부분만 수정을 거쳤다.

if older_dict[topping[i]]! == 1 {
            older_dict[topping[i]]! -= 1
            older_count -= 1
        }
        else if older_dict[topping[i]]! > 1 {
            older_dict[topping[i]]! -= 1
        }

채점 결과

정확성: 100.0
합계: 100.0 / 100.0

굿 !

최종코드

import Foundation

func solution(_ topping: [Int]) -> Int {
    var answer = 0
    let LEN = topping.count

    var younger = Set<Int>()
    var older_dict = [Int: Int]()
    topping.forEach { older_dict[$0, default: 0] += 1 }
    var older_count = older_dict.count // 총 종류 개수
    print(older_dict)

    for i in 0 ..< LEN {
        younger.insert(topping[i])
        if older_dict[topping[i]]! == 1 {
            older_dict[topping[i]]! -= 1
            older_count -= 1
        }
        else if older_dict[topping[i]]! > 1 {
            older_dict[topping[i]]! -= 1
        }
        if younger.count == older_count {
            answer += 1
        }
    }
    return answer
}

타인의 코드

import Foundation

func solution(_ topping:[Int]) -> Int {
    var answer = 0
    var idx = 0
    var me = [Int: Int](), brother = [Int: Int]()
    topping.forEach { 
        me[$0, default: 0] += 1
    }

    topping.forEach { 
        me[$0]! -= 1
        brother[$0, default: 0] += 1
        if me[$0]! == 0 { me[$0] = nil } 
        if me.keys.count == brother.keys.count {
            answer += 1
        }
    }

    return answer
}