카카오 2020겨울인턴 코딩테스트 해답 코드

Question1.swift

import Foundation

func solution(_ board:[[Int]], _ moves:[Int]) -> Int {
    var b = board
    var st: [Int] = []
    var result = 0

    for m in moves {
        var index = 0
        while index < b.count,b[index][m-1] == 0 {
            index += 1
        }

        if index == b.count {
            continue
        }

        st.append(b[index][m-1])
        b[index][m-1] = 0

        while st.canDeleteDolls() {
            st.popLast()
            st.popLast()
            result += 2
        }
    }

    return result
}

extension Array where Element == Int {
    func canDeleteDolls() -> Bool {
        guard self.count > 1 else {
            return false
        }

        let top = self[self.count-1]
        let topUnder = self[self.count-2]

        return top == topUnder
    }
}

Question2.swift

import Foundation

func solution(_ s:String) -> [Int] {
    var result: [Set<Int>] = []

    let secondIndex = s.index(after: s.startIndex)
    let lastIndex = s.index(before: s.endIndex)

    var num = 0
    var temp: Set<Int> = Set()
    var isInSet: Bool = false
    for c in s[secondIndex..<lastIndex] {
        if c.isNumber {
            num *= 10
            num += Int(String(c))!
        } else if c == Character(",") {
            if isInSet {
                temp.insert(num)
                num = 0
            }
        } else if c == Character("}") {
            if num != 0 {
                temp.insert(num)
            }
            result.append(temp)
        } else if c == Character("{") {
            isInSet = true
            num = 0
            temp = Set()
        }
    }

    let sorted = result.sorted { $0.count < $1.count }

    var prev: Set<Int> = Set()
    var r: [Int] = []

    for s in sorted {
        r.append(s.symmetricDifference(prev).first!)
        prev = s
    }
    return r
}

Question3.swift

import Foundation

func solution(_ user_id:[String], _ banned_id:[String]) -> Int {
    var candidate: [[String]] = []
    var s: Set<Set<String>> = Set()

    for id in banned_id {
        let c = user_id.getCandidate(id)

        candidate.append(c)
    }

    getProjections(candidate, 0, []) {

        var t: Set<String> = Set()

        for a in $0 {
            t.insert(a)
        }

        if t.count != $0.count {
            return
        }

        s.insert(t)
    }

    return s.count
}

func getProjections(_ s: [[String]], _ i: Int,
                    _ result: [String],
                    _ c: ([String]) -> Void) {

    if i == s.count {
        c(result)
        return
    }

    var result = result
    for t in s[i] {

        if !result.contains(t) {
            result.append(t)
            getProjections(s, i+1, result, c)
            result.popLast()
        }
    }
}

extension Array where Element == String {
    func getCandidate(_ id: String) -> [String] {
        var candidate: [String] = []

        for s in self {
            guard id.count == s.count else {
                continue
            }
            var isMatched = true
            for (c1,c2) in zip(s,id) {
                if c2 == Character("*") {
                    continue
                }

                if c1 != c2 {
                    isMatched = false
                    break
                }
            }

            if isMatched {
                candidate.append(s)
            }
        }

        return candidate
    }
}


solution(["123","456","789"], ["*23"])

Question4.swift

import Foundation

func solution(_ k:Int64, _ room_number:[Int64]) -> [Int64] {
    var result: [Int64] = []
    var dic: [Int64:Int64] = [:]

    for number in room_number {
        let n = dic.getRoomNumber(number)

        result.append(n)
    }
    return result
}

extension Dictionary where Key == Int64, Value == Int64 {
    mutating func getRoomNumber(_ n: Int64) -> Int64{
        guard let s = self[n] else {
            self[n] = n + 1
            return n
        }

        let newRoom = getRoomNumber(s)
        self[n] = newRoom

        return newRoom
    }
}

Question5.swift

import Foundation

func solution(_ stones:[Int], _ k:Int) -> Int {
    var arr: [Range<Int>] = []

    let ordered = stones.enumerated().sorted { $0.element < $1.element }
    var total = 0
    var index = 0
    var prevCount = 0

    while index < stones.count {
        let toBeHovered = ordered[index].element - prevCount // 이 돌이 가라앉기 까지 건넌 사람
        prevCount = ordered[index].element
        total += toBeHovered

        let sinked = ordered[index].offset

        if !arr.insertAndMerge(sinked..<sinked+1, k) {
            break
        }
        index += 1
    }

    return total
}

extension Array where Element == Range<Int> {
    func binarySearch(_ r: Range<Int>) -> Int {
        if self.isEmpty {
            return 0
        }

        var lower = 0
        var upper = self.count-1

        while lower <= upper {
            let mid = (lower + upper) / 2

            let founded = self[mid]

            if founded.lowerBound < r.lowerBound {
                lower = mid + 1
            } else {
                upper = mid - 1
            }
        }

        return lower
    }

    mutating func insertAndMerge(_ r: Range<Int>, _ limit: Int) -> Bool {
        var i = self.binarySearch(r)
        var current = r


        if i>0, self[i-1].upperBound == current.lowerBound {
            let d = self.remove(at: i-1)
            current = d.lowerBound..<current.upperBound
            i -= 1
        }

        if i<self.count, self[i].lowerBound == current.upperBound {
            let d = self.remove(at: i)
            current = current.lowerBound..<d.upperBound
        }

        self.insert(current, at: i)

        if current.upperBound - current.lowerBound >= limit {
            return false
        }

        return true
    }
}