문제 설명
두 개의 문자열 배열 a1과 a2를 입력받는 JavaScript 함수를 작성해야 합니다. 각 문자열은 알파벳 소문자 a부터 z까지만으로 구성되며, x는 첫 번째 배열의 임의의 문자열, y는 두 번째 배열의 임의의 문자열이라고 가정합니다.
함수는 다음 값을 찾아 반환해야 합니다.
max(abs(length(x) − length(y)))
즉, 두 배열에 속한 모든 문자열 쌍 (x, y)에 대해 길이 차이의 절댓값을 계산한 뒤, 그중 가장 큰 값을 구하는 문제입니다.
접근 방법
모든 문자열 조합을 일일이 비교하면 O(n×m)의 시간이 필요하지만, 더 효율적인 방법이 있습니다. 최대 절대 차이는 반드시 다음 두 값 중 하나이기 때문입니다.
- 첫 번째 배열의 최대 길이와 두 번째 배열의 최소 길이의 차이
- 두 번째 배열의 최대 길이와 첫 번째 배열의 최소 길이의 차이
따라서 각 배열에서 가장 긴 문자열과 가장 짧은 문자열의 길이만 구하면 O(n+m) 시간 복잡도로 문제를 해결할 수 있습니다. 또한 어느 한쪽 배열이라도 비어 있다면 비교 자체가 불가능하므로 -1을 반환하도록 처리합니다.
예제 코드
const arr1 = ["hoqq", "bbllkw", "oox", "ejjuyyy", "plmiis", "xxxzgpsssa", "xxwwkktt", "znnnnfqknaz", "qqquuhii", "dvvvwz"];
const arr2 = ["cccooommaaqqoxii", "gggqaffhhh", "tttoowwwmmww"];
const findMaxAbsDiff = (arr1 = [], arr2 = []) => {
// 어느 한쪽 배열이 비어 있으면 -1 반환
if (arr1.length === 0 || arr2.length === 0) {
return -1;
}
// 각 배열에서 문자열 길이만 추출
const l1 = arr1.map(str => str.length);
const l2 = arr2.map(str => str.length);
// 두 경우 중 더 큰 값이 최대 절대 차이
return Math.max(
Math.max(...l1) - Math.min(...l2),
Math.max(...l2) - Math.min(...l1)
);
};
console.log(findMaxAbsDiff(arr1, arr2));
실행 결과
13
동작 원리
위 예제에서 arr2의 가장 긴 문자열인 "cccooommaaqqoxii"의 길이는 16이고, arr1의 가장 짧은 문자열인 "oox"의 길이는 3입니다. 따라서 최대 절대 차이는 16 − 3 = 13이 됩니다.
이처럼 최댓값과 최솟값만 활용하면 이중 반복문으로 모든 조합을 비교하는 방식보다 훨씬 빠르고 간결하게 문제를 해결할 수 있습니다.