1월 25일 TIL

프로그래머스 코딩테스트 [ 과일 장수 ]

Github 링크

• 이 문제는 주어진 정수 배열을 m 만큼 나누고, 나눠진 배열의 최소 값을 m 만큼 곱하고 총 합을 구하고, 최대치의 합을 구하는 문제다.
• 처음에는 배열을 오름차순으로 정렬 한 다음에, m개 만큼 Array를 자르고, 해당 SubArray에서 제일 작은 수를 찾고, 곱하고, 합의 추가해준다음에, SubArray만큼 Array에서 자르는 방식으로 했는데, 시간초과가 떴다. 아래는 초기 코드다

import Foundation

func solution(_ k:Int, _ m:Int, _ score:[Int]) -> Int {
    var scores = Array(score.sorted().reversed())
    var ans = 0

    while(scores.count >= m){
        var mIndex = scores.index(scores.startIndex,offsetBy:m)
        var min = scores[scores.startIndex..<mIndex].min()!
        ans += min * m
        scores.removeSubrange(0..<m) 
    }
    return ans
}

• 여기서 시간초과가 나올만한 부분이 어딜까 고민을 해봤는데,
• 우선 mIndex 여기 부분에서는 O(n)이 소요 된다. Array.index(_:offsetBy:) 메서는 매번 배열을 순회하고 인덱스를 계산해서 시간 복잡도가 O(n)이라고 한다.
• array.min()도 마찬가지로 O(m) 시간복잡도를 갖고,
• array.removeSubrange(0..<m)도 마찬가지로 O(m)의 시간복잡도를 갖는다.
• 그래서 보완한게 아래 코드다.

import Foundation

func solution(_ k: Int, _ m: Int, _ score: [Int]) -> Int {
    var scores = Array(score.sorted().reversed())
    var ans = 0
    
    while scores.count >= m {
        let subArray = Array(scores.prefix(m))
        let minValue = subArray.min()!
        ans += minValue * m
        scores.removeFirst(m)
    }
    
    return ans
}

• prefix(m)를 사용해서 index 함수를 사용하지 않았기에, O(m) 시간 복잡도를 갖고
• min()은 어쩔수 없으니깐 O(m)
• removeFirst()도 마찬가지로 O(m)을 갖게 된다.
• 즉 처음만 O(n) -> O(m)으로 바꾼것이다. 결과는 똑같이 시간초과.
• 그래서 그러면 한번에 chunk로 나누면 되지 않을까??? 생각을 해서 인터넷 찾아서 한게 Array.chunked() 메서드를 찾았다. 근데 이건 기본제공해주는게 아니라 extenstion을 써야하는거네??? 이건 아닌것 같아서 다른방법을 생각해봤다.
• 생각해보니깐 굳이 나눠야 할까 라는 생각을 하게 되었다. 그냥 index만 이용하면 되는거 아니야? 생각해보니깐 어쩌피 배열은 내림차순으로 정렬이 되어 있고, m개로 나눈다고 생각하면, m * 횟수 index 만 보면 알아서 제일 작은 값이겠네? 그래서 새로 코드를 짜봤다.

import Foundation

func solution(_ k: Int, _ m: Int, _ score: [Int]) -> Int {
    var scores = Array(score.sorted().reversed())
    var index = m-1
    var ans = 0
    while index < score.count {
        ans += scores[index] * m 
        index += m
    } 
    return ans
}

• ????? 너무 간단한거 아닌가? 뭘 한거지.. 정말 알고리즘 문제 풀때마다 느끼는거지만 많이 풀어봐야하고, 너무 복잡하게 생각할 필요가 없는것 같다.
• 다른사람 풀이를 봤는데, 나랑 똑같은 사람도 있지만 더 간단하게 푼 분도 있었다.

import Foundation

func solution(_ k:Int, _ m:Int, _ score:[Int]) -> Int {
    let s = score.sorted(by: >)
    return stride(from: m-1, to: score.count, by: m)
        .reduce(0) { $0 + s[$1] * m }
}

• stride(from: 시작점 , to: 종료점 (포함안됨), by : 얼마만큼) 반복하는 Strideable 프로토콜을 준수하는 값들의 시퀸스가 return 된다. Strideable 프로토콜에서도 reduce(_:combine) 메서드를 사용할 수 있다.
• 그러면 reduce(0) {$0 + s[$1] * m} 은 무엇을 의미하느냐, 일단 reduce(0)은 초기값 0을 설정해주는것이고, 여기서 $0은 지금까지의 누적값, $1은 현재 요소를 의미한다.
• 정리하면, stride메서드를 통해서 m-1부터 score.count까지 m 만큼 증가하는 시퀸스를 만들고, 해당 시퀸스를 순회하면서 해당 요소를 인덱스로 갖고 있는 s 배열의 값을 m이랑 곱해주면서 누적값과 추가해주면서 최종 누적값을 return 하는 것이다.
• 결과적으로 내가 짠 코드랑 똑같이 작동하지만, 확실히 가독성면에서 뛰어나기 때문에, 추후에는 저렇게 사용해보자.

프로그래머스 코딩테스트 [ 모의 고사 ]

Github 링크

• 이 문제는 주어진 패턴을 사용해서 기존의 배열과 비교해서 제일 정답을 많이 맞춘 패턴을 출력하는 문제이다.
• 나는 단순히 주어진 배턴들을 Array에 넣고, 모든 패턴들의 길이를 answer와 맞추기 위해서 패턴을 반복하기, answer의 사이즈만큼 자르고 했는데 다 풀고 다른사람이 푼 방법을 보니깐 굉장히 깔끔하다고 느껴져서 참고용으로 갖고와봤다.

import Foundation

func solution(_ answers:[Int]) -> [Int] {
    let answer = (
        a: [1, 2, 3, 4, 5], // index % 5
        b: [2, 1, 2, 3, 2, 4, 2, 5], // index % 8
        c: [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] // index % 10
    )
    var point = [1:0, 2:0, 3:0]

    for (i, v) in answers.enumerated() {
        if v == answer.a[i % 5] { point[1] = point[1]! + 1 }
        if v == answer.b[i % 8] { point[2] = point[2]! + 1 }
        if v == answer.c[i % 10] { point[3] = point[3]! + 1 }
    }

    return point.sorted{ $0.key < $1.key }.filter{ $0.value == point.values.max() }.map{ $0.key }
}

• 우선 키 값이 a,b,c인 dictionary를 만들고, 각각의 value로는 각각의 패턴을 Array로 넣어줬다.
• 그리고 각각의 학생의 점수를 표시해줄 point 딕셔너리를 만들고, 여기서 a:0 이런식으로 만들지 않은건 마지막 정답 부분때문에 그렇다.
• 그리고 밑에서는 for (i,v) in answers.enumerated() 를 통해 answers의 인덱스와 해당 하는 값을 순회하고, 확인한다. 만약 answers의 값이 answer a 학생의 [i%5] 이런식으로 접근해서, 굳이 배열을 늘리고 이럴 필요가 없다.
• 이제 각 학생의 점수를 다 구했다면, 해당 배열을 오름차순으로 정렬하고, (여기서 굳이 $0.key < $1.key를 쓴 이유는 Dictionary는 정렬할려면 기준을 정해줘야 한다.) 정렬한 Dictionary의 대해서 filter를 사용해서 해당 배열의 max()와 비교해서 같은것들만 dictionary을 또 다시 만들고, 해당 Dictionary.map{$0.key}를 통해 key값만 갖고 있는 배열을 만들기 위해서 이다.
• 개인적으로 return 전까지는 할 수 있지만, return 딱 한줄로 이렇게 코딩한다는것은 정말 대단한것 같다.

프로그래머스 코딩테스트 [ 기사단원의 무기 ]

Github 링크

• 이 문제는 주어진 1부터 주어진 숫자까지 각각 약수 개수의 합을 구하는 문제인데. 당연히 나는 뭐야? 약수 구하는 문제는 이미 쉽자나, 나름 시간초과까지 생각해서 sqrtN으로 함수 만들어서 했는데,어떤 사람이 풀이 한거를 봤는데 정말 색달라서 참고용으로 공유하려고 한다.

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var attack = [Int](repeating: 0, count: number+1)

    for i in 1...number {
        var c = i

        while c <= number {
            attack[c] += 1
            c += i
        }
        print(attack)
    }
    attack = attack.map { $0 > limit ? power : $0 }
    return attack.reduce(0, +)
}

• 처음에 봤을때는 뭐야 약수를 애초에 구한적이 없는거 아니야? 생각을 했는데, 다시보니 attack을 print해서 보니깐 뭔가 좀 대단한것 같다는 생각을 했다.
• 우선 0으로 반복되는 number+1 만큼의 배열을 만들었다. number +1 은 index편하게 하려고 그런것 같다.
• 중요한건 while c <= number 여기인데, 로직을 한번 생각해보니깐, c = i 이기 떄문에, 1 부터 number까지 반복하고, 1,2,3,4..number 이런식으로, 1로 예시를 들어보자.
• c 는 1이고, c는 number보다 작으니 while 문이 실행되고, attack[1] 을 하나를 증가한다, 그리고 c는 1만큼 또 증가. 이걸 attack[number] 까지 하고, 다시 c = 2, 마찬가지로 c 는 number 보다 작으니, while문 실행, 근데 이번엔 attack[2] 만 1 증가, 그리고 c는 2만큼 증가. attack[4] 1만큼 증가, 뭔가 느낌이 딱 오는게, c는 약수이고, c를 약수로 갖고 있는 숫자는 당연히 c의 배수라는것이다.
• 예를 들면 i 가 7 이면, c 도 7 이고, c 는 i 만큼 즉 7 만큼 증가하니깐 14, 당연히 배수니깐 해당 index의 숫자 -> 숫자 는 당연히 c를 약수로 갖고 있는것이다.
• 만약 이게 숫자 하나의 약수를 찾는 문제였다면, 결국은 brute force이기 때문에 전혀 대단한 방법이 아니지만, 1부터 특정 숫자까지 약수 개수를 찾는거기 때문에, 이렇게 하면 O(n* log(n))의 시간복잡도를 갖는다.
• 약수를 하나하나 찾는 코드는 sqrt를 썼더라도 O(n * sqrt(n))의 시간복잡도를 갖지만, 저 방법도 n이 엄청 크지 않는 상황에서도 써먹을수도 있을꺼 같다. 어쨋든 새로운 방법으로 생각하는것도 좋은 자세인것 같다.

프로그래머스 코딩테스트 [ 옹알이(2) ]

Github 링크

• 이 문제는 애기가 딱 네 단어만 말할 수 있고, 해당 단어로만 구성하고, 연속된 같은 단어가 없는 단어의 개수를 찾는 문제이다.
• 이 문제 풀때 난 되게 비효율적이지만 참신하다고 생각했는데, 사람들이 다 String.replacingOccurrences 로 풀었다.
• 일단 주어진 단어에서 애기가 말할 수 있는 4단어를 각각 1,2,3,4로 변환했다.
• 그리고 변환된 단어에서 만약 연속된 11,22,33,44,가 있는지 확인하고 혹은 알파벳이 남아 있는지도 확인을 하는 방법이다.
• 연속된 글자가 있는지 확인하느거랑 알파벳 확인하는거는 언젠가는 또 쓸꺼 같아서 밑에 남겨놓을려고 한다.

func checkRepeating(_ string: String) -> Bool {
	// optional 쓰는 이유는 첫번째 char랑 비교할께 없어서 
    var previousChar: Character?
    
    for char in string {
        if let previous = previousChar, char == previous {
            return true
        }
        previousChar = char
    }
    return false
}

func checkAlphabet(_ string: String) -> Bool {
    for char in string{
        if !char.isNumber {
            return true
        }
    }
    return false
}