[21/08/15 KATA NINJA] 토스 NEXT && 블록이동하기 && 외벽점검
토스NEXT
프론트엔드만 풀 수 있는 코딩테스트였다.
- Promise All
문제를 적기는 두려워서 안되겠고, 가장 생각나는건..
Promise.all을 몰라 틀렸다는 점
요청을 배열을 순회하며 진행하게 되면, 요청에 걸리는 시간 * n번만큼 시간을 쓰게되지만, Promise ALL을 사용하여 코드하게되면, 훨씬 더 빠르게 가능
- 클로저
5번 문제가 클로저 문제였는데, 초반에 좀 어려움을 겪었다.
클로저를 자주 사용하지 않다보니, 조금 시간이 오래걸린거 같다. 맞게 풀긴했는데, 코드가 좀 지저분해져서 걱정이다
그 밖에 6 7 8번은 6번 끄적인거 말고는 손도 못댔고, 4번은 이해자체를 못했다.
이런 코딩테스트가 좀 더 반갑지만
너무 어렵다..!
블록 이동하기
bfs에 익숙하지 않아서 시간이 오래걸렸다. 다른 사람들은 왠지 쉽게 풀었을 것 같은? 느낌의 문제.
최단시간을 구하려면 bfs가 좋다는 사실도 오늘 깨닫게 되었다. dfs로 하게되면 모든 경로를 다 조사하며, 최솟값을 구하게되므로, depth가 깊어지고 자식이 많을 수록 오래걸린다.
bfs로 풀게되면 최단거리가 자식 탐색 도중에 나오게되므로, 훨씬 빠르다
리팩토링 이전의 코드
function solution(board) {
function validate(fr, fc, sr, sc, visited) {
return (
isContact(fr, fc) &&
isContact(sr, sc) &&
board[fr][fc] === 0 &&
board[sr][sc] === 0 &&
!visited.includes(`${fr}${fc},${sr}${sc}`)
);
}
function isContact(r, c) {
return r >= 0 && r < board.length && c >= 0 && c < board.length;
}
function rotate(front, back, visited) {
const array = [];
const fr = +front[0];
const fc = +front[1];
const sr = +back[0];
const sc = +back[1];
// front를 축으로 돌린다
if (fr === sr) {
if (
validate(fr - 1, fc, fr, fc, visited) &&
isContact(sr - 1, sc) &&
board[sr - 1][sc] === 0
) {
array.push(`${fr - 1}${fc},${fr}${fc}`);
array.push(`${sr - 1}${sc},${sr}${sc}`);
}
if (
validate(fr, fc, fr + 1, fc, visited) &&
isContact(sr + 1, sc) &&
board[sr + 1][sc] === 0
) {
array.push(`${fr}${fc},${fr + 1}${fc}`);
}
}
if (fc === sc) {
if (
validate(fr, fc, fr, fc + 1, visited) &&
isContact(sr, sc + 1) &&
board[sr][sc + 1] === 0
) {
array.push(`${fr}${fc},${fr}${fc + 1}`);
array.push(`${sr}${sc},${sr}${sc + 1}`);
}
if (
validate(fr, fc - 1, fr, fc, visited) &&
isContact(sr, sc - 1) &&
board[sr][sc - 1] === 0
) {
array.push(`${fr}${fc - 1},${fr}${fc}`);
array.push(`${sr}${sc - 1},${sr}${sc}`);
}
}
return array;
}
function move(front, back, visited) {
let array = [];
const nx = [-1, 0, 1, 0];
const ny = [0, -1, 0, 1];
const fr = +front[0];
const fc = +front[1];
const sr = +back[0];
const sc = +back[1];
nx.forEach((i, idx) => {
if (
validate(
fr + nx[idx],
fc + ny[idx],
sr + nx[idx],
sc + ny[idx],
visited
)
) {
// 이동이 가능한 경우
array.push(
`${fr + nx[idx]}${fc + ny[idx]},${sr + nx[idx]}${sc + ny[idx]}`
);
}
});
return array;
}
var answer = Number.MAX_SAFE_INTEGER;
var nn = `${board.length - 1}${board.length - 1}`;
// function DFS(current, visited) {
// // if (visited.includes(current)) return;
// const [front, back] = current.split(",");
// if (front === nn || back === nn) {
// if (answer > visited.length) {
// answer = visited.length;
// }
// return;
// }
// rotate(front, back, visited).forEach((r) => {
// DFS(r, [...visited, current]);
// });
// move(front, back, visited).forEach((m) => {
// DFS(m, [...visited, current]);
// });
// }
// DFS("00,01", []);
let queue = [["00,01", 0]];
let visited = ["00,01"];
while (queue.length !== 0) {
const [current, dep] = queue.shift();
// if (visited.includes(current)) return;
const [front, back] = current.split(",");
if (front === nn || back === nn) {
return dep;
}
rotate(front, back, visited).forEach((r) => {
visited.push(r);
queue.push([r, dep + 1]);
});
move(front, back, visited).forEach((m) => {
visited.push(m);
queue.push([m, dep + 1]);
});
}
return answer;
}
console.log(
solution([
[0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 1, 0, 0, 0, 0],
])
);
외벽점검
로직은
dist배열을 순회하며,
각 요소별로 시간대 배열을 브루투 포스하며, 제일 작업을 많이 할때의 갯수를 구해 저장한다.
friend
배열에 요소들이 다 채워지면 친구들의 조합을 이용하여 모든 외벽을 점검할 수 있을때 까지 점검하여 리턴하도록한다.
아직 다 못풀었음... 어디 수정해야할지 감이안온다.
function getAllCombination(array){
const combination = []
function DFS(cur,currentNumber,r){
if(cur.length === r){
combination.push(cur);
return ;
}
for(let check=currentNumber+1;check<array.length;check++){
DFS([...cur,array[check]],check,r);
}
}
for(let check=0;check<array.length;check++){
DFS([],-1,check+1)
}
return combination;
}
function solution(n, weak, dist) {
var friends = []
dist.forEach((fr,idx)=>{
let max = 0;
for(const start of [...new Array(n)].map((i,idx)=>idx)){
let Jeongjeomgeom = 0;
let Yeokjeomgeom = 0;
weak.forEach(w=>{
let jeong = w;
if(start > jeong){
jeong+=n;
}
if(fr+start >= jeong ){
Jeongjeomgeom++;
}
let yeok = w;
if(start < yeok){
yeok -= n;
}
if( yeok >= start-fr){
Yeokjeomgeom++;
}
})
max = Math.max(max,Jeongjeomgeom,Yeokjeomgeom);
}
friends[idx] = max;
})
const combi = getAllCombination(friends.map((f,idx)=>idx));
for(let c of combi){
let gong =0
c.forEach(index=>gong+=friends[index])
if(gong>=weak.length){
return c.length;
}
}
return -1;
}
Author And Source
이 문제에 관하여([21/08/15 KATA NINJA] 토스 NEXT && 블록이동하기 && 외벽점검), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rat8397/210815-KATA-NINJA-토스-NEXT-블록이동하기-외벽점검저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)