알고리즘 지식 정리(10월 14일)[프로그래머스 레벨 1]

직사각형 별찍기

func myPrint (_ a:Int,_ b:Int) {
    for i in 0..<b {
        print(Array(repeating: "*", count: a).joined())
    }
}

Array(repeating:String,count:Int)로 String 타입의 배열 생성 후, joined()로 단일 String로 변경

 

최대공약수와 최소공배수

func _solution(_ n:Int, _ m:Int) -> [Int] {
    var myMax = min(n,m)
    while true {
        if max(m,n)%myMax==0 && min(m,n)%myMax==0 {
            break
        } else {
            myMax-=1
        }
    }
    var myMin = 1
    while true {
        if ((myMax*myMin)%n==0 && (myMax*myMin)%m==0) {
            break
        } else {
            myMin+=1
        }
    }
    return [myMax,myMin*myMax]
}

굉장히 무식하게 while문과 %를 사용해 원초적으로 접근하였다. 시간복잡도 상 시간초과가 있을 것 같았으나, 그런 문제는 아직 없었다.

 

func gcd(_ a: Int, _ b: Int) -> Int {
    let mod: Int = a % b
    return 0 == mod ? min(a, b) : gcd(b, mod)
}

func lcm(_ a: Int, _ b: Int) -> Int {
    return a * b / gcd(a, b)
}

func solution(_ n:Int, _ m:Int) -> [Int] {
    return [gcd(n, m), lcm(n, m)]
}

최소공배수와 최대공약수를 구하는 공식은 좀 외워야할 필요가 있을듯하다.

최대공약수의 경우, 재귀호출을 통해서 두개의 값에 나머지 연산자를 지속 적용하여 완벽히 나누어 떨어질때까지 나머지연산자와 두 값중 작은 값으로 연산을 반복하고 있다. (완전히 이해하기에 좀 시간이 걸릴듯하다)

최소공배수는 양 값의 곱에 최대공약수를 나눠주면 된다.

 

예산

func solution(_ d:[Int], _ budget:Int) -> Int {
    let myArr = d.sorted()
    var sum = 0
    var ans = 0
    for i in 0..<d.count {
        if sum+myArr[i] <= budget {
            sum+=myArr[i]
            ans+=1
        } else {
            break
        }
    }
    return ans
}

최대한 많은 부서를 지원하기 위해선, 적은 금액을 신청한 부서부터 요청을 수락해야한다. 이에 sorted로 배열을 오름차순으로 정렬한 후에, for문으로 매 부서마다 예산이 오바되지 않는지를 누적금액인 sum과 비교하면서 파악하였고, 오바되지 않을 경우, ans에 1을 더하였다. 만일 오바될 경우 for문을 break하도록 하여 불필요한 추가연산을 막았다.

 

3진법 뒤집기

func radixChange(_ n:Int) -> Int {
    return Int(String(String(n,radix: 3).reversed()),radix:3)!
//    return Int(String(String(n,radix: 3).reversed()),radix: 10)! // 이게 아니다...
}

어이없게 좀 시간이 많이 소요된 문제인데, Int(n,radix:Int) 함수는 3진법 정수로 해석하여, 10진법 정수로 변환하는 것이다.

 

크기가 작은 부분문자열

func partialString(_ t:String, _ p:String)->Int {
    let myArr = t.enumerated().compactMap{(id,ch) in return id<=Array(t).count-Array(p).count ? String(Array(t)[id..<id+Array(p).count]) : nil}
    return myArr.filter{Int($0)!<=Int(p)!}.count
}

조금 코드가 더러운데, compactMap을 통해 nil을 반환하는 값은 자동으로 filter가 되게끔 하였고, myArr에 부분 문자열을 추가하는 과정에 존재하지 않는 id를 접근하는 것을 막고자, enumerated로 id값 접근, t와 p의 String 길이값을 활용해 id의 상한선을 조건문으로 추가하였다.

 

감사합니다.