Summary

1. 실제 시간에 맞춰 푼 문제

• [0] 신고 결과 받기 (83.8/100)        - 시간초과

• [0] k진수에서 소수 개수 구하기 (88/100) - 시간초과

• [0] 주차 요금 계산 (100/100)        

2. 시간 제한 없이 풀어서 푼 문제

• [0] 파괴되지 않은 건물 (100/100) (0/0) - 효율성 빵점

3. 풀었든 못풀었든 해당 문제 어떻게 접근했는지

• [0] 양궁대회

• [X] 양과 늑대

• [X] 사라지는 발판

Lv1. 신고 결과 받기

문제) 2022 KAKAO BLIND RECRUITMENT - 신고결과 받기

접근방식

1. report(각 이용자가 신고한 이용자의 ID)에 중복된 데이터(동일한 유저에 대한 신고횟수는 1회로 처리되기 때문) 제거
2. 신고데이터 만들기 : 반복문으로 report Item의 두번째 항목(이름)을 가져와서 id_list에 이름이 있으면 id_list자리수배열항목에 1을 더한다.
3. id_list에 경고받은 아이디가 있을 경우, id_list의 index를 가져와 신고데이터의 index번째 개수가 k개 이상이면 결과를 담을 배열에 1을 더한다.

구현코드

import Foundation

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    
    // 중복 제거
    var dup = Array(Set(report))
    var warningMail = Array(repeating: 0, count: id_list.count)
    var resultMail = Array(repeating: 0, count: id_list.count)
    
    for (index, val) in dup.enumerated() {
        let arr = val.components(separatedBy: " ")
        let warnId = arr[1]
        
        // report에서의 index
        if let idIndex = id_list.firstIndex(of: warnId) {
            // 경고 개수 카운트
            warningMail[idIndex] += 1
        }   
    }
    // 경고 메일
    // warningMail = warningMail.map { $0 >= k ? 1 : 0}
    
    for (index, val) in dup.enumerated() {
        let arr = val.components(separatedBy: " ")
        let id = arr[0]
        let warnId = arr[1]
        
        // report에서의 index
        if let warnIdIndex = id_list.firstIndex(of: warnId) {
            // 자기가 신고한 경고메일 수신 개수가 k이상이라면
            if warningMail[warnIdIndex] >= k {
                if let idIndex = id_list.firstIndex(of: id) {
                    resultMail[idIndex] += 1
                }
            }
        }   
    }

    return resultMail
}

소요시간
45분
풀이결과
처음 결과를 잘못 도출해서 돌아갔다.
시간복잡도를 다시생각해봐야겠다.

Lv2. k진수에서 소수 개수 구하기

문제) 2022 KAKAO BLIND RECRUITMENT - k진수에서 소수 개수 구하기

접근방식

1. k 진수를 만드는 함수, 소수판별 함수를 만든다.
2. 조건에 맞는 수를 추출한다 -> 다행히 0으로 split해야한다는 거를 빨리 접근했다.
3. 반복문을 돌리면서 소수판별해서 소수일경우 result를 count한다.

구현코드

import Foundation

func solution(_ n:Int, _ k:Int) -> Int {
    
    var result = 0
    // 인수로 변환
    let kNum = makeKnum(n, k)

    let split = kNum.components(separatedBy: "0")
    
    for n in split {
        result += isPrime(Int(n) ?? 0)
    }
    return result
}

// k 진수 만들기
func makeKnum(_ n:Int, _ k:Int) -> String {
    var result = ""
    var num = n
    
    if k == 10 { return "\(n)"}

    while num != 0 {
        result += "\(num % k)"
        num /= k
    }
    return String(result.reversed())
}

func isPrime(_ n: Int) -> Int {
    if n == 0 || n == 1 { return 0 }
    if n == 2 { return 1 }
    if n % 2 == 0 { return 0 }
    
    for i in 3..<n {
        if n % i == 0 {
            return 0
        }
    }
    return 1
}

풀이결과
20분
풀이결과
쉬웠다.

Lv2. 주차 요금 계산

문제) 2022 KAKAO BLIND RECRUITMENT - 주차 요금 계산

접근방식

1. 입차하는 차는 무조건 queue에 넣는다.
2. 출차하는 차는 번호를 확인해서 queue같은 번호의 차가 있는 지 확인하고, queue 출차하는 차의 번호가 있다면 queue에서 제거하고, 계산해야되는 배열에 넣는다. (번호, 입차시간, 출차시간)
3. 만약 queue에 남아있으면 다 빼서 출차시간은 23:59 고정으로 (번호, 입차시간, 23:59) 계산해야되는 배열에 넣는다.
4. 계산해야하는 배열을 입력받아 총 주차시간을 계산해주는 함수를 구현한다.
5. 총 주차시간과 요금표 정보를 통해 결과를 구한다.

구현코드

import Foundation

func solution(_ fees:[Int], _ records:[String]) -> [Int] {
    
    var queue = [[String]]()
    // 계산해야 할 배열
    var receipt = [[String]]()
    
    for rec in records {
        let arr = rec.components(separatedBy: " ")
        let time = arr[0]
        let no = arr[1]
        let isIn = arr[2]
        
        if isIn == "IN" {
            queue.append(arr)
        } else {
            if let index = getInRecordsSameCarNo(queue, no), index != -1 {
                var tmp = [String]()
                tmp.append(no)
                tmp.append(queue[index][0])
                tmp.append(time)
                
                receipt.append(tmp)
                queue.remove(at: index)
            }
        }
    }
    
    // 큐에 아직 남아 있다면.
    
    while !queue.isEmpty {
        let record = queue.first!
        var tmp = [String]()
        tmp.append(record[1])
        tmp.append(record[0])
        tmp.append("23:59")
                
        receipt.append(tmp)
        queue.removeFirst()
    }

    let parkingTime = calcTotalParkingTime(records: receipt)

    return getResult(parkingTime, fees: fees)
}

// 요금표와 누적주차시간(분)을 받아 요금을 계산하는 함수
func calcParkingFee(fees: [Int], totalParkingMinutes: Int) -> Int {
    var result = 0
    
    let basicTime = fees[0]
    let basicFee = fees[1]
    let unitTime = fees[2]
    let unitFee = fees[3]
    
    // 누적주차시간이 기본시간 이하 일때, 기본 요금 청구
    if totalParkingMinutes - basicTime <= 0  { return basicFee }
    
    let ceiledTime = (totalParkingMinutes - basicTime) % unitTime == 0 ? (totalParkingMinutes - basicTime) / unitTime : ((totalParkingMinutes - basicTime) / unitTime) + 1
    result = basicFee + (ceiledTime * unitFee)
    
    return result
}

func calcTotalParkingTime(records: [[String]]) -> [String: Int] {
    var result = [String: Int]()
    
    for record in records {
        let carNo = record[0]
        let start = record[1]
        let end = record[2]
        
        let totalParkingTime = getParkingTime(start, end)
        
        if let recordResult = result[carNo] {
            result[carNo] = recordResult + totalParkingTime
        } else {
            result[carNo] = totalParkingTime
        }
    }
    
    
    return result
}

// 시간차이 구하는 함수 (start: HH:mm, end: HH:mm)
func getParkingTime(_ start: String, _ end: String) -> Int {
    let format = DateFormatter()
    format.dateFormat = "HH:mm"

    guard let startTime = format.date(from: start) else {return 0}
    guard let endTime = format.date(from: end) else {return 0}
    
    let useTime = Int(endTime.timeIntervalSince(startTime))
    
    return (useTime  % 3600) / 60 + ((useTime / 3600) * 60)
}

func getInRecordsSameCarNo(_ queue: [[String]], _ carNo: String) -> Int? {
    for (index, val) in queue.enumerated() {
        if val[1] == carNo {
            return index
        }
    }
    return -1
}

func getResult(_ dict: [String: Int], fees: [Int]) -> [Int] {
    
    var result = [String: Int]()
    
    for (key, val) in dict {
        result[key] = calcParkingFee(fees: fees, totalParkingMinutes: val)
    }
    
    return Array(result.sorted { $0.0 < $1.0 }.map{$0.1})
}

소요시간
40분
풀이결과
시간차이 구하는 함수 구현하는게 시간이 걸렸다.
그리고 변수 사용하면서 사소하게 조건이 틀어져서 시간이 걸렸다.

Lv2. 양궁대회

문제) 2022 KAKAO BLIND RECRUITMENT - 양궁대회
이해 참고링크

접근방식

1. 0번째 영역(0점 영역)까지 도달하면 라이언의 경기의 모든 경우를 나타내는 트리의 leaf노드에 도달했다는 뜻이므로 남은 화살을 모두 사용한다. (남은 함수를 모두 0점에 놓는 이유는 가장 낮은 점수를 많이 맞히는 것이 유리하기 때문이다.)

구현코드

import Foundation

var resultCandis:[[Int]] = []
func getResult() {
	// 여기서 i는 현재 비교하고자 하는 '가장 낮은 점수'를 가리킨다.
    for i in stride(from: 10, to: 0, by: -1) {
        if resultCandis.count == 1  {
            return
        }
        let max:Int = resultCandis.map{ $0[i] }.max() ?? 0
        resultCandis = resultCandis.filter{ $0[i] == max }
    }
}

var maxGap:Int = 0
var infoA:[Int] = [] // 어피치의 점수판
func dfs(_ i:Int, _ n:Int, _ rArr:[Int], _ rScore:Int, _ aScore:Int) {
	// 10번째 영역(0점 영역)까지 도달하면 라이언의 경기의 모든 경우를 나타내는 트리의 leaf노드에 도달했다는 뜻이므로 남은 화살을 모두 사용한다. 
    // 남은 함수를 모두 0점에 놓는 이유는 가장 낮은 점수를 많이 맞히는 것이 유리하기 때문이다.
    if i == 10 {
        let gap = rScore - aScore
        if gap > 0 {
            if gap > maxGap {
                maxGap = gap
                resultCandis = [rArr+[n]]
            } else if gap == maxGap {
                resultCandis.append(rArr+[n])
            }
        }
        return
    }
    
    let winNum:Int = infoA[i]+1 
    // 라이언이 점수를 획득하는 경우 (이길 수 있는 화살이 남아있을 때만 가능)
    if n >= winNum {
        dfs(i+1, n-winNum, rArr+[winNum], rScore + 10 - i, aScore)
    }
    // 라이언이 점수를 획득하지 않는 경우 (만약 둘다 0개의 화살을 맞혔다면 둘다 점수를 얻지 못함
    let aPoint:Int = infoA[i] == 0 ? 0 : 10 - i
    dfs(i+1, n, rArr+[0], rScore, aScore + aPoint)
}

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    infoA = info
    
    dfs(0, n, [], 0, 0)
    
    if resultCandis.isEmpty {
        return [-1]
    } else {
        getResult() // resultCandis에 하나만 남기기 위한 함수 호출
        return resultCandis[0]    
    }
}

소요시간
풀지 못함.
풀이결과
dfs조건 찾는 연습을 해야겠다.

Lv3. 양과 늑대

문제) 2022 KAKAO BLIND RECRUITMENT - 양과 늑대
이해참고링크

접근방식

구현코드

import Foundation

func solution(_ info:[Int], _ edges:[[Int]]) -> Int {
    var total = 0
    var visited = Array(repeating: false, count: info.count)
    visited[0] = true

    DFS(1, 0)
    
    func DFS(_ curSheep: Int, _ curWolf: Int) {
        if curSheep <= curWolf {
            return
        } else {
            total = max(total, curSheep)
        }
        
        for edge in edges {
            let parent = edge[0]
            let child = edge[1]
            let nextState = info[child] == 0 ? (1, 0) : (0, 1)
            if visited[parent] && !visited[child] {
                visited[child] = true
                DFS(curSheep + nextState.0, curWolf + nextState.1)
                visited[child] = false
            }
        }
    }
    return total
}

소요시간
못품! -분 (문제 이해 - 5분, 접근 방식 - -분, 구현 - -분)
풀이결과
백트래킹을 사용해야 하나?

Lv3. 파괴되지 않은 건물

문제) 2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물

접근방식

1. board를 skill만큼 반복문을 돌면서 skill에 해당하는 칸일경우 내구도를 갱신시킨다. (완전탐색..으로)
2. 마지막 내구도에서 0보다 큰 값들을 count에서 return 하는 함수 구현

구현코드

import Foundation

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    var result = board
    
    for s in skill {
        let r1 = s[1]
        let r2 = s[3]
        let c1 = s[2]
        let c2 = s[4]
        let degree = s[5]
        //let cRange = 
        var isAttack = s[0] == 1 ? true : false
        
        for i in 0..<board.count {
            for j in 0..<board.first!.count {
                if isAttack {
                    if i >= r1 && i <= r2 && j >= c1 && j <= c2 {
                        result[i][j] -= degree
                    }
                } else {
                    if i >= r1 && i <= r2 && j >= c1 && j <= c2 {
                        result[i][j] += degree
                    }
                }
            }
        }
    }
    return getNotDestoriedBuilding(result)
}

// 내구도가 0보다 작은 건물의 개수
func getNotDestoriedBuilding(_ board:[[Int]]) -> Int {
    return board.flatMap {$0}.filter {$0 > 0}.count
}

소요시간
30분 (문제 이해 - 5분, 접근 방식 - 5분, 구현 - 20분)
풀이결과
백트래킹을 사용해야 하나? 누적합?
시간초과...