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

K번째 수

func solution(_ array:[Int], _ commands:[[Int]]) -> [Int] {
    return commands.map{$0.map{$0-1}}.map{ array[$0[0]...$0[1]].sorted()[$0[2]]}
}

주어진 commands 배열의 경우 배열용 id에서 1이 더해진 값을 담고 있었기 때문에,  map{$0.map{$0-1}} 고차함수를 적용해 2차원 배열 내부 값들을 일괄 변경해주었다.

그 이후에 범위 연산자를 통해 array의 일부 영역에 접근, 오름차순 정렬 후 $0[2]번째 값을 접근하였다.

 

두 개 뽑아서 더하기

func solution(_ numbers:[Int]) -> [Int] {
    var ans:[Int] = []
    for i in 0..<numbers.count {
        for j in i+1..<numbers.count {
            ans.append(numbers[i]+numbers[j])
        }
    }
    return Array(Set(ans)).sorted()
}

2중 포문으로 각기 다른 id값을 참조하도록 구성한 후, ans에 더한값 추가. 중복된 값은 피해야하기 때문에 Set로 변경한 후에, sorted() 적용하였다.

 

푸드 파이트 대회

func solution(_ food:[Int]) -> String {
    let myStr = food[1...].enumerated().map{Array(repeating: String($0.offset+1), count: $0.element/2).joined()}.joined()
    return myStr+"0"+myStr.reversed()
}

Array(repeating:String,count:Int)와 .joined() 함수를 조합하여 반복적인 String값들을 결합한 후 단일 String으로 변환하였고, String 타입에 적용가능한 reversed() 메서드를 최종적용하여 가운데 0을 중심으로 대칭되게끔 하였다.

 

문자열 내 마음대로 정렬하기

func sortString(_ strings:[String], _ n:Int) -> [String] {
    return strings.sorted {
        if Array($0)[n]==Array($1)[n]{
            return $0<$1
        } else {
            return Array($0)[n]<Array($1)[n]
        }
    }
}

sorted() 메서드는 시간복잡도가 O(nlogn)으로 높다. 따라서 sorted().sorted{ ... }로 적용할 경우, 시간 초과가 발생한다.

오름차순을 적용해야하는 것은 n번째 텍스트가 동일할때에만이기 때문에 sorted 클로저에 상황을 분기처리하여 하나의 sorted 메서드로 구현하고자 하였다.

더 찾아보니 sorted 메서드는 사본을 생성하는 함수이기에, 그 자체로 sort보다 메모리를 두 배 사용한다고 한다.

func sortString(_ strings:[String], _ n:Int) -> [String] {
    var arr = strings
    arr.sort {
        if Array($0)[n]==Array($1)[n]{
            return $0<$1
        } else {
            return Array($0)[n]<Array($1)[n]
        }
    }
    return arr
}

따라서, 코드가 추가되더라도 추가 변수를 생성한 후에 sort를 실행할 경우 훨씬 더 빠르게 코드가 실행됨을 확인할 수 있었다.

 

콜라 문제

func solution(_ a:Int, _ b:Int, _ n:Int) -> Int {
    var ans = 0
    func recc(_ cnt:Int){ // 남은 병 수
        if cnt<a{
            return
        }
        ans+=(cnt/a)*b // 돌려받는 병 수
        return recc((cnt/a)*b+cnt%a)
    }
    recc(n)
    return ans
}

오랜만에 재귀함수 형태로 풀어보았다. a,b 변수를 접근하기 위해 남아있는 병수를 전달받는 재귀함수 recc을 solution 함수 내부에 선언하였으며, 재귀함수에는 남은 병수가 새 콜라를 받을 수 있는 최소 병수보다 적을 경우 종료되는 로직, 아닐 경우 돌려받는 병수를 누적시켜주고 재실행하는 로직을 구현해주었다.

마지막으로 재귀함수가 종료되면, 누적시킨 ans 변수값을 반환하게끔 구성하였다.

 

감사합니다.