문제 내용
You are given a 0-indexed integer array
mapping which represents the mapping rule of a shuffled decimal system. mapping[i] = j means digit i should be mapped to digit j in this system.The mapped value of an integer is the new integer obtained by replacing each occurrence of digit
i in the integer with mapping[i] for all 0 <= i <= 9.You are also given another integer array
nums. Return the array nums sorted in non-decreasing order based on the mapped values of its elements.Notes:
•
Elements with the same mapped values should appear in the same relative order as in the input.
•
The elements of
nums should only be sorted based on their mapped values and not be replaced by them.입출력 예
Example 1:
Input: mapping =[8,9,4,0,2,1,3,5,7,6], nums =[991,338,38]
Output:[338,38,991]
Example 2:
Input: mapping =[0,1,2,3,4,5,6,7,8,9], nums =[789,456,123]
Output:[123, 456, 789]
입출력 예 설명
입출력 예 #1
Map the number 991 as follows:
1. mapping[9] = 6, so all occurrences of the digit 9 will become 6.
2. mapping[1] = 9, so all occurrences of the digit 1 will become 9.
Therefore, the mapped value of 991 is 669.
338 maps to 007, or 7 after removing the leading zeros.
38 maps to 07, which is also 7 after removing leading zeros.
Since 338 and 38 share the same mapped value, they should remain in the same relative order, so 338 comes before 38.
Thus, the sorted array is
[338,38,991].입출력 예 #2
789 maps to 789, 456 maps to 456, and 123 maps to 123. Thus, the sorted array is
[123,456,789].접근 1
mapping과 nums 설명을 보면 다음과 같습니다.
mapping[i] = jmeans digitishould be mapped to digitjin this system.
즉, number가 554인 경우, ‘5’, ‘5’, ‘4’가 mapping배열의 인덱스로 적용되어 숫자가 할당되는 방식입니다.
그림으로 그리면 아래와 같아요.
number: 554
digit 1 = 5 -> mapping[5]
digit 2 = 5 -> mapping[5]
digit 3 = 4 -> mapping[4]
이렇게 기존 숫자를 매핑한 숫자로 변환하여 정렬을 수행하면 됩니다.
만약 같은 값인 경우 기존의 정렬순서에 맞게 정렬해야하는 조건이 있으나 이는 Swift의 sorted메서드 내에서 안정정렬이 이루어지므로 크게 신경쓸 필요는 없습니다.
매핑된 숫자로정렬하고난 뒤의 기존 숫자 위치를 출력해주어야하므로, 매핑된 숫자와 기존 숫자를 묶어줄 필요가 있겠죠?
이를 수행하면 다음과 같습니다.
각 nums라는 배열의 요소마다 convert함수를 호출하여 mapping된 숫자와 원래 숫자를 튜플로 감쌌습니다.
그 이후 sorted 메서드의 클로저로 mapped에 대한 정렬기준을 제시한 뒤, 원래 숫자로 변환하는 식으로 해결할 수 있습니다.
repeat - while구문으로 작성한 이유는, number가 0인 경우도 존재하기 때문에, 최소한 한 번 실행을 보장하기 위해섭니다.개선: 재귀적으로 접근하기
위에서 구현한
convert메서드의 while문을 봐볼까요?var mappedNumber = 0
var number = originalNumber
var base = 1
repeat {
mappedNumber += mapping[number % 10] * base
number /= 10
base *= 10
} while number != 0
처음에는 일의 자리 숫자부터 더하기 시작해서 점점 십의자리, 백의자리를 접근할 수 있도록 number를 10으로 나누고, 각 자릿수에 맞게 더해주기 위해 base라는 변수에 10을 반복해서 곱하고 있어요.
그러면 number는 점점 오른쪽부터 숫자가 하나씩 사라져갈 거예요(9876, 987, 98, 9 …) 순으로요.
반면에 base는 (1, 10, 100, 1000)으로 자릿수를 맞춰줄 거예요.
모든 숫자들에 대해서 일의 자리, 십의 자리, 백의 자리, … 만큼의 수를 mapping으로 환산하는 것을 반복문이 아닌 재귀로도 처리해볼 수 있을 거예요.
private func mapped(_ mapping: [Int], _ number: Int, _ base: Int = 1) -> Int {
if number < 10 { // 마지막 숫자까지 도달한 경우
base * mapping[number % 10]
} else {
base * mapping[number % 10] + mapped(mapping, number / 10, base * 10)
}
}
위에서 반복문으로 정의한 걸 단순히 재귀로 수정한 것 뿐이에요.
이제 문제를 다시 풀어봅시다.
여기, 태초에 제공받는 number가 있습니다.
nums
여기서 저희는 위처럼 원래 숫자인
nums와 매핑된 숫자를 갖는 mappedNumber를 튜플로 가질 겁니다. 이건 nums.map(_:)을 사용해서 이 클로저 내부에 mapped메서드를 대입해서 mappedNumber를 얻을 수 있어요.(nums, nums.map({ mapped(mapping, $0) }))
각 배열 요소에 대해 짝을 지어주기 위해
zip을 사용해볼 수 있을 겁니다. [A, B, C]와 [1, 2, 3]이 있는 경우 (A, 1), (B, 2), (C, 3)과 같이 짝지어주고 싶을 때 zip이 유용하죠.zip(nums, nums.map({ mapped(mapping, $0) }))
그리고 위에서 처리한 대로 mappedNumber 기준으로 정렬하고, 원래 숫자배열로 되돌리면 됩니다.
zip(nums, nums.map({ mapped(mapping, $0) }))
.sorted { $0.1 < $1.1 }
.map(\.0)