코린이 탈출기
[2019 KAKAO BLIND RECRUITMENT][JAVASCRIPT] 길 찾기 게임 본문
코딩테스트 연습 - 길 찾기 게임
[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]
programmers.co.kr
걸린 시간 : 1시간
<문제 Logic>
1. nodeInfo 배열에 node 번호를 추가해준다.
2. nodeInfo 배열을 y값 기준으로 내림차순, 같은경우 x값 기준으로 오름차순 정렬한다.
3. myOrder 함수를 재귀적으로 호출하는데, nodeInfo 배열을 돌면서 가장 첫번째 원소의 x값 기준으로 그 값보다 작으면 left 배열에 추가, 크면 right 배열에 추가한다. nodeInfo의 가장 첫번째 원소는 항상 서브트리의 root가 된다.
4. 전위순회인 경우 탐색 순서가 root->left->right 이므로 함수의 첫부분에 써주면 되고, 후위탐색인 경우 탐색순서가 left->right->root이므로 재귀 호출을 다 완료한 다음 제일 마지막에 해주면 된다.
5. nodeInfo의 길이가 0인 경우는 더이상의 서브트리가 존재하지 않는다는 의미이므로 재귀 호출을 중단한다.
-전체 코드-
<!DOCTYPE html>
<body>
<script>
let preorder = [];
let postorder = [];
function myOrder(nodeinfo, preorder, postorder)
{
if(nodeinfo.length == 0)
return;
let now_idx = 0;
let left = [];
let right = [];
console.log(nodeinfo);
preorder.push(nodeinfo[now_idx][2]);
for(let i = now_idx +1; i<nodeinfo.length; i++)
{
if(nodeinfo[i][0] < nodeinfo[now_idx][0])//부모노드보다 왼쪽에 위치
{
left.push(nodeinfo[i]);
}
else//부모노드보다 오른쪽에 위치
{
right.push(nodeinfo[i]);
}
}
myOrder(left, preorder, postorder);
myOrder(right, preorder, postorder);
postorder.push(nodeinfo[now_idx][2]);
}
function solution(nodeinfo) {
var answer = [];
let graph = [];
for(var i = 0; i<nodeinfo.length; i++)
{
nodeinfo[i].push(i+1);
}
nodeinfo.sort((a,b)=>{
if(a[1] < b[1])
return 1;
else if(a[1] > b[1])
return -1;
else{
if(a[0] > b[0])
return 1;
else
return -1;
}
})
console.log(nodeinfo);
myOrder(nodeinfo, preorder, postorder)
console.log(preorder);
console.log(postorder);
answer.push(preorder);
answer.push(postorder);
console.log(answer);
return answer;
}
solution([[5, 3], [11, 5], [13, 3], [3, 5], [6, 1], [1, 3], [8, 6], [7, 2], [2, 2]]);
</script>
</body>'문제 풀이' 카테고리의 다른 글
| [2018 KAKAO BLIND RECRUITMENT][JAVASCRIPT] 뉴스 클러스터링 (0) | 2020.09.11 |
|---|---|
| [2018 KAKAO BLIND RECRUITMENT][JAVASCRIPT] 셔틀버스 (0) | 2020.09.11 |
| [2019 KAKAO BLIND RECRUITMENT][JAVASCRIPT] 무지의 먹방라이브 (0) | 2020.09.07 |
| [2019 KAKAO BLIND RECRUITMENT][JAVASCRIPT] 후보키 (0) | 2020.09.06 |
| [2019 KAKAO BLIND RECRUITMENT][JAVASCRIPT] 실패율 (0) | 2020.09.05 |