서로 다른(distinct) 정수로 이루어진 배열 arr과, 정수 배열들을 요소로 가지는 배열 sourceArr이 주어집니다. sourceArr 내부의 정수들 역시 중복되지 않는다고 가정합니다.
우리가 작성해야 할 함수는 sourceArr에 포함된 하위 배열들을 임의의 순서로 이어 붙여(concatenate) 목표 배열 arr을 완성하는지 판별합니다.
단, 한 가지 중요한 제약 조건이 있습니다. 각 하위 배열 내부의 정수들은 절대 재배치할 수 없습니다. 이 조건을 지키면서 arr을 만드는 것이 가능하면 true, 불가능하면 false를 반환해야 합니다.
문제 예시
const arr = [23, 67, 789]; const sourceArr = [[23], [789, 67]];
위 경우 함수는 false를 반환해야 합니다. 하위 배열 [789, 67] 내부의 요소 순서를 바꿀 수 없기 때문에, 어떤 순서로 연결하더라도 목표 배열 [23, 67, 789]를 만들 수 없습니다.
접근 방법
이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다.
1. 각 하위 배열의 첫 번째 요소를 키로 삼아, 해당 하위 배열의 위치를 저장하는 인덱스 맵을 만듭니다.
2. 목표 배열 arr을 앞에서부터 순회하면서, 현재 값으로 시작하는 하위 배열을 찾습니다.
3. 찾은 하위 배열의 모든 요소가 arr의 연속된 구간과 순서대로 일치하는지 검사합니다.
4. 하나라도 불일치하거나 적절한 시작 하위 배열이 없으면 즉시 false를 반환하고, 끝까지 통과하면 true를 반환합니다.
구현 코드
const arr1 = [23, 67, 789];
const arr2 = [23, 789, 67];
const sourceArr = [[23], [789, 67]];
const validFormation = (arr, sourceArr) => {
const indexes = new Array(100);
let arrIndex = 0;
let index;
// 각 하위 배열의 첫 번째 요소를 기준으로 인덱스 맵 생성
for (let i = 0; i < sourceArr.length; ++i) {
indexes[sourceArr[i][0]] = i;
}
// 목표 배열을 순차적으로 매칭
while (arrIndex < arr.length) {
index = indexes[arr[arrIndex]];
if (index === undefined) return false;
for (let j = 0; j < sourceArr[index].length; ++j) {
if (arr[arrIndex] !== sourceArr[index][j]) return false;
++arrIndex;
}
}
return true;
};
console.log(validFormation(arr1, sourceArr));
console.log(validFormation(arr2, sourceArr));실행 결과
false true
결과 해설
arr1 = [23, 67, 789]의 경우, [23] 다음에 이어 붙일 수 있는 하위 배열은 [789, 67]뿐입니다. 그러면 23 뒤에 789가 오게 되어 목표 배열의 두 번째 값인 67과 일치하지 않으므로 false입니다.
반면 arr2 = [23, 789, 67]은 [23] + [789, 67]을 순서대로 연결하면 정확히 일치하므로 true입니다.
참고 사항
위 구현은 고정 크기 배열(new Array(100))을 인덱스 맵으로 사용하기 때문에, 정수 값이 100 미만이라는 전제가 필요합니다. 입력 범위가 제한적이지 않은 실무 환경에서는 Map 객체나 일반 객체를 사용해 동일한 로직을 구현하는 것이 더 안전하고 확장성이 좋습니다.