알고리즘 문제를 풀었다…..
문서가 주어지는데 각 문서마다 중요도가 담겨져있다. 문서와 중요도가 주어질때에 중요도에 따라서 문서를 출력하는 배열을 만드시오.
조건 문서는 50개까지만 들어올 수 있다. 1 ~ 9 까지의 중요도를 가지고 있고, 더 높거나, 낮으면 버린다. 같은 중요도일 경우에는 나중에 들어오는 문서가 더 먼저 출력된다.
예제
const test1d = ['A', 'B', 'C', 'D'];
const test1i = [2, 1, 4, 3];
const output1 = ['C', 'D', 'A', 'B'];
const test2d = ['A', 'B', 'C', 'D', 'E'];
const test2i = [1, 3, 2, 2, 4];
const output2 = ['E', 'B', 'D', 'C', 'A'];
const test3d = ['A', 'B', 'C', 'D', 'E'];
const test3i = [1, 12, 0, 1, 4];
const output3 = ['E', 'D', 'A'];
처음에는 for문 안에 for문으로 O(n^2)으로 생각을 했지만 이건 좋지 못한 시간복잡도이기 때문에 어떻게 하면 시간복잡도를 줄일수 있을지 고민을 했다.
그러던중 테이블에 나누어 담으면 O(n)으로 문제를 해결할 수 있을 것이라고 생각했다.
우선 중요도가 1 ~ 9 까지 정해져 있었기 때문에 1 ~ 9 까지의 table을 만들어서 나누어 담기로 했다. 그리고 문서를 순서대로 확인하면서 각 table에 담았다.
각 테이블을 다시 확인하며 하나의 문자로 모아서 배열로 만들어 줌으로써 문제를 해결할 수 있었다. 시간복잡도에 대해서 고민을 하고 해결하는 좋은 문제였다고 생각한다.
function printNum(documentArray, importance) {
let result = '';
// 테이블 생성
const bin = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const table = {};
bin.forEach(binNum => (table[binNum] = []));
// 테이블마다 문서 담기
documentArray.forEach((document, index) => {
if (0 < importance[index] && importance[index] < 10) {
table[importance[index]].push(document);
}
});
// 각 테이블을 확인하면서 결과 생성
bin.forEach(bin => {
if (table[bin].length > 0) {
table[bin].forEach(document => {
result = document + result;
});
}
});
return result.split('');
}
생성한 각 테이블에 받은 문서들을 분배해준다. 분배를 할 때에는 중요도안에 있는지 체크를 해준다.
각 테이블을 순서대로 확인하면서 결과변수에 담아서 출력한다. 쉬운 문제지만 자료구조를 이용하고 시간복잡도를 생각하면서 풀어서 의미가 있었다.