토스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;
}