프로그래머스 lv3 -가장먼노드

2020 07 14 - 효율성까지 맞췄다!

---

• 너무먼~ 것은 찾지 못한다 (시간초과로..)
• 테스트케이스 1~6은 맞는데, 7~9는 시간초과로 알 수없당ㅎㅎ;
  아니 무슨 2만개 씩이나... 더 생각을 해봐야겠다 어케시간을 줄일지

1.코드

function solution(n, edge) {
    let queue = [1];
    let visited = [1];
    while(visited.length < n){
      let size = queue.length;
      for( let i=0; i<size; i++){
          let num = queue.shift();
          let tempArr = [];
          edge.forEach(e=> e.includes(num) ? tempArr.push(e): null );
          for (let arr of tempArr){
              let filtered = arr.filter(e=> !visited.includes(e));
              queue.push(...filtered);
              visited.push(...filtered);
          }
      }
  }
    return queue.length;
}

• 추가

2.코드

효율성때문에 조금 손봤다. (그래서 테케 1개더 풀수있다)
그러나 여전히 8,9는 못한다 속도넘쳐서

function solution(n, edge) {
    let queue = [1];
    let visited = [1];
    while(visited.length < n){
      let size = queue.length;
      for( let i=0; i<size; i++){
          let num = queue.shift();
          for (let i=0; i<edge.length; i++){
            if(edge[i].includes(num)){
              let filtered = edge[i].filter(e=> !visited.includes(e));
              queue.push(...filtered);
              visited.push(...filtered);
            }
          }
      }
  }
    return queue.length;
}

3. set

• 기존 visited를 set으로 바꾸면 속도가 빨라지긴 한다.
  8번 제외 모두 속도안에 되지만 갑자기 2번에 오류가 생기고
  여전히 8번은 안되서...
• 언제 가장먼 그 노드님을 찾게될까

4. 정답!!

function solution(n,edge){
    let queue = [1];
    let visited = [1];
    while(visited.length < n){
      let size = queue.length;
      for(let i=0; i<size; i++){
          let num = queue.shift(); 
          for (let j=0; j<edge.length; j++){
            if(edge[j].includes(num)){
              let filtered = edge[j].filter(e=> !visited.includes(e))
              queue.push(...filtered);
              visited.push(...filtered);
              edge.splice(j,1);
                j--;
            }
          }
         
      }  
  }
    return queue.length;
}

뭐 여전히 느리긴 하다. 그러나 프로그래머스 문제 기준엔 맞아서 정답이 되었으니... 만족한다!

방법 자체는 조금 무식한 방법인 것 같기도 하다.

수정한 부분은, 매번 전체 edge배열을 도는게 비효율 적이라서

이미 돈 배열은 삭제시키는 방법으로 순회 시간을 단축시켰다.

어차피 처음엔 무조건 다 돌긴 해야된다. 얼마나 많은 배열이 1번과 만날지도 모르며, 이어지는 다른 숫자들이 순서대로인지 어쩐지 모르기 때문이다.