swift 코딩테스트 기초, 최솟값만들기 계수정렬 풀이

 

 

 

 

 

프로그래머스 1단계 문제, 최솟값 만들기 문제링크 ▼

코딩테스트 연습 - 최솟값 만들기

 

 

 

---

프로그래머스 1단계 문제, 최솟값 만들기 문제 설명

프로그래머스 1단계문제, 최소값 만들기는 먼저, 길이가 같은 a, b 배열이 주어집니다. 이 각각의 배열에서 숫자를 하나씩 빼서 곱한 값을 누적해서 더하는 작업을 수행할 때 최종적으로 누적된 값이 최소가 되도록 만드는 문제입니다.

 

입출력 예시 아래에서 보겠습닌다.

 

 

---

프로그래머스 최솟값 만들기 문제 입출력 예시

[1, 4, 2]	[5, 4, 4]	29
[1,2]	[3,4]	10

길이가 같은 두개의 배열이 주어졌을때 각 배열의 숫자를 뽑아서 곱한 누적합의 최소값을 구하면 됩니다. 해당문제는 각 배열을 오름차순 정렬 후, A[index] * B[A.count - index - 1] 을 진행해나가면 최소 누적합을 구할 수 있습니다. 

 

위 첫행의 입력 예시를 토대로 적용해보자면 A, B 배열을 각각 정렬합니다. [1, 2, 4] / [4, 4, 5]가 되지요. 여기에서 인덱스를 0...2로 순회하면서 A[index] * B[A.count - index - 1] 곱의 누적합을 구하면, 1 * 5 + 2 * 4 + 4 * 4 == 29가 되며 이는 곱의 최소 누적합이 됩니다. 

 

이를 코드로 적용해보겠습니다. 해당 문제의 정렬을 할때 Array에서 기본적으로 접근해서 사용 가능한 sort(), sorted()를 사용해도 문제를 통과할 수 있지만 해당 정렬함수의 시간복잡도는 O(NlogN) 입니다. 본 문제의 숫자 범위는 최대 1,000에 불과하므로, 계수정렬을 사용해서 O(N)의 시간복잡도로 풀 수도 있습니다. 

 

기본 sorted(), sort() 함수로 사용하는건 재미없으니(?) 계수정렬로 풀어보도록 하겠습니다.

 

 

 

---

프로그래머스 1단계 문제, 최솟값 만들기 swift 풀이
Array extension, 계수정렬 함수 구현

풀다보니 본 문제의 코드 대부분은 계수정렬 구현이 되었습니다. [Int] Array extension에 계수정렬 결과를 배열로 반환하는 커스텀 메서드를 구현했습니다. 

 

5 ~ 7행) dic 배열에 현재 있는 값들을 인덱스로 기록합니다. 

8 ~ 16행) 1 ~ mx 값까지 오름차순으로 인덱스를 순회하면서 dic[num]이 1 이상일 경우(값이 있을 경우) 해당 값을 반환할 배열, result에 차례대로 적재합니다. cnt를 통해 카운팅을 하면서 전체 값을 기록했는지를 체크합니다. 만약 모든 요소를 찾아서 오름차순으로 result 배열에 저장했을 경우, result 배열을 그대로 반환합니다. 

 

이렇게 O(N) 시간복잡도로 배열을 정렬해서 반환하는 커스텀 기능을 구현했습니다. 이제 이어서 solution 함수를 채워보겠습니다.

 

 

 

---

Array reduce 활용, 결과값 연산하기

22 ~ 23행) 앞서 제가 말했던 접근방식대로, A, B 배열을 오름차순 정렬했습니다.

24행) aArray의 enumerated()를 사용해서 (인덱스, 값) 튜플 배열을 반환한 후 이어서 reduce를 통해 곱의 누적합을 수행하고 있습니다. answer에 A, B 배열의 곱을 차례대로 누적합 적용하여 answer를 반환하게 됩니다. 

 

- (answer, pair) in 정의를 하지 않고, $0, $1로 인자값을 접근할 수도 있습니다.
- 인덱스와 값을 의미하는 offset, element의 이름을 사용하는 대신 tuple에 0, 1의 형태로 숫자를 접근해서 사용할 수도 있습니다.

 

이렇게 계수정렬을 직접 구현해서 본 문제를 풀어봤습니다. 실제로 내장함수 sorted, sort를 사용하는 다른 분들 코드보다 몇배 이상 빠른 결과를 확인 할 수 있었습니다. 관련 의견 있으시면 언제든 댓글 달아주세요.

 

 

---

프로그래머스 최솟값 만들기
코드 제출결과 & swift언어 전체코드

extension Array where Element == Int {
    func sortedArray() -> [Int] {
        let mx = self.max()!
        var result: [Int] = []
        var dic = [Int](repeating: 0, count: mx + 1)
        var cnt = 0
        self.forEach { dic[$0] += 1 }
        for num in (1...mx) {
            while dic[num] > 0 {
                result.append(num)
                dic[num] -= 1
                cnt += 1
            }
            if cnt == self.count { break }
        }
        return result
    }
}

func solution(_ A: [Int], _ B: [Int]) -> Int
{
    let aArray = A.sortedArray()
    let bArray = B.sortedArray()
    return aArray.enumerated().reduce(into: 0) { (answer, pair) in
        answer += pair.element * bArray[bArray.count - pair.offset - 1]
    }
}