엄격하게 증가하는 수열이란?
수열이 엄격하게 증가(Strictly Increasing)한다는 것은 arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] 조건을 만족한다는 의미입니다. 즉, 인접한 두 원소가 같은 값을 가지지 않으면서 항상 이전 값보다 커야 합니다.
문제 설명
두 개의 숫자 배열 arr1과 arr2를 각각 첫 번째, 두 번째 인자로 받는 JavaScript 함수를 작성해야 합니다.
우리는 두 배열에서 같은 인덱스에 있는 원소끼리 자유롭게 교환(swap)할 수 있습니다. 다시 말해 arr1[i]와 arr2[i]를 서로 바꿀 수 있다는 뜻입니다. 함수는 두 수열 모두 엄격하게 증가하도록 만들기 위해 필요한 최소 교환 횟수를 반환해야 합니다.
예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
입력
const arr1 = [1, 3, 5, 4]; const arr2 = [1, 2, 3, 7];
출력
const output = 1;
출력 설명
arr1[3]의 값 4와 arr2[3]의 값 7을 서로 교환하면 arr1은 [1, 3, 5, 7]이 되고, arr2는 [1, 2, 3, 4]가 됩니다. 이렇게 하면 두 배열 모두 엄격하게 증가하는 수열이 되므로 필요한 최소 교환 횟수는 1입니다.
풀이 접근: 동적 계획법(DP)
각 인덱스에는 "교환함(true)"과 "교환하지 않음(false)"이라는 두 가지 상태만 존재합니다. 따라서 각 위치에서 두 상태별 최소 교환 횟수를 저장하면서 배열을 앞에서부터 순차적으로 살펴보면 문제를 효율적으로 해결할 수 있습니다.
- true 상태: 현재 인덱스에서 교환을 수행했을 때의 최소 교환 횟수
- false 상태: 현재 인덱스에서 교환을 수행하지 않았을 때의 최소 교환 횟수
상태 전환이 가능한지는 다음 두 조건으로 판단합니다.
- 교환하는 경우: arr1[i] > arr2[i - 1] && arr2[i] > arr1[i - 1]을 만족하면 교환한 뒤에도 수열이 유지됩니다.
- 교환하지 않는 경우: arr1[i] > arr1[i - 1] && arr2[i] > arr2[i - 1]을 만족하면 그대로 두어도 수열이 유지됩니다.
코드 구현
다음은 위 접근 방식을 구현한 코드입니다.
const arr1 = [1, 3, 5, 4];
const arr2 = [1, 2, 3, 7];
const findSwaps = (arr1 = [], arr2 = []) => {
// true: 교환함, false: 교환하지 않음
let map = {
true: 1,
false: 0,
};
for (let i = 1; i < arr1.length; i++) {
const current = {
true: Infinity,
false: Infinity,
}
// 현재 인덱스에서 교환하는 경우
if (arr1[i] > arr2[i - 1] && arr2[i] > arr1[i - 1]) {
current.true = Math.min(
current.true,
map.false + 1,
)
current.false = Math.min(
current.false,
map.true)
}
// 현재 인덱스에서 교환하지 않는 경우
if (arr2[i] > arr2[i - 1] && arr1[i] > arr1[i - 1]) {
current.true = Math.min(
current.true,
map.true + 1,
)
current.false = Math.min(
current.false,
map.false)
}
map = current
}
return Math.min(
map.false,
map.true)
}
console.log(findSwaps(arr1, arr2));실행 결과
1
마무리
이 풀이는 각 인덱스를 한 번씩만 순회하므로 시간 복잡도는 O(n)이며, 상태를 저장하는 데 상수 크기의 변수만 사용하므로 공간 복잡도는 O(1)입니다. "교환 여부"라는 두 가지 상태만 추적하면 되기 때문에 가능한 모든 조합을 탐색하지 않고도 최소 교환 횟수를 효율적으로 구할 수 있습니다.