[36번] [상] 키패드 누르기 (미완)

프로그래머스

 

 

아직 해결 못함!!!

이 문제는 참으로 고난이도다..ㅠㅠ

 처음에 어떻게 접근할지도 생각이 나지를 않아서, 경로를 찾는 알고리즘을 찾다가, DFS, BFS 개념을 들여다 봤고, 그러다 키패드 자료구조를 짜야 탐색도 가능하기에 이진 트리 -> 이중연결 트리 - > 그래프 -> 가중 그래프 -> 다익스트라 알고리즘 이렇게 엄청나게 빠르게 훑었다.

 

우선, 그래프 자료구조를 만들고, 그래프 DFS (재귀 사용) 방법 비스므리하게 구현을 했는데, 결국 전체 테스트를 통과하지는 못했다. 이미 너무 지쳐서 다시 코드를 보지는 못했다. 내일 짬 날때 꼭 보려고 한다.

 

 * [카카오인턴] 키패드 누르기
 * 양손 엄지로만 키패드를 누를 수 있고, 상하좌우 4방향으로만 이동, 한 번에 1칸만 가능
 * 147 - 왼손, 369 - 오른손, 2580 - 더 가까운 손
 * 양손의 길이가 같다면, 오른손 잡이는 오른손, 왼손잡이는 왼손으로 누름
 * 주어진 입력번호 배열을 어느 손으로 눌렀는지 반환

 

알고리즘 강의를 보면서 적용하며 만드느라, 슈도코드를 따로 작성하지는 못했다.. 

성공하면 작성해보기로..ㅎㅎ

function solution(numbers, hand) {
  let result = [];
  let curL = "*",
    curR = "#";
  for (let n of numbers) {
    if (n == 2 || n == 5 || n == 8 || n == 0) {
      let v = keypad.isAdj(n, curL, curR, hand);
      result.push(v);
      if (v === "L") curL = n;
      else curR = n;
    } else if (n == 1 || n == 4 || n == 7 || n == "*") {
      result.push("L");
      curL = n;
    } else if (n == 3 || n == 6 || n == 9 || n == "#") {
      result.push("R");
      curR = n;
    }
  }
  return result.join("");
}

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
  isAdj(n, l, r, h) {
    const adj = this.adjacencyList;
    if (adj[n].includes(l) && adj[n].includes(r)) {
      if (h === "left") return "L";
      else return "R";
    } else if (adj[n].includes(l)) return "L";
    else if (adj[n].includes(r)) return "R";
    // n이 l과 r의 바로 근접 값이 아니라면, l과 r에서 출발해서 n에 도달하기까지의 거리를 비교해서 짧은 쪽을 반환 (l => n vs r => n)
    else {
      let dL, dR;
      function findDistance(start, end, dist) {
        let distList = [];
        let visited = {};
        visited[start] = true;

        (function fD(s, d) {
          let exam = adj[s].filter(
            (e) => e === 2 || e === 5 || e === 8 || e === 0
          );
          exam.forEach((e) => {
            if (visited[e]) {
              return;
            } else if (!visited[e] && !adj[e].includes(end)) {
              visited[e] = true;
              d++;
              return fD(e, d);
            } else {
              d++;
              return distList.push(d);
            }
          });
        })(start, dist);
        return Math.min(...distList);
      }

      dL = findDistance(l, n, 0);
      dR = findDistance(r, n, 0);
      if (dL === dR) {
        if (h === "left") {
          return "L";
        } else {
          return "R";
        }
      } else if (dL > dR) {
        return "R";
      } else return "L";
    }
  }
}

let keypad = new Graph();
for (let i = 0; i < 10; i++) {
  keypad.addVertex(i);
}
keypad.addVertex("*");
keypad.addVertex("#");

keypad.addEdge(1, 2);
keypad.addEdge(1, 4);
keypad.addEdge(2, 3);
keypad.addEdge(2, 5);
keypad.addEdge(3, 6);
keypad.addEdge(4, 5);
keypad.addEdge(4, 7);
keypad.addEdge(5, 6);
keypad.addEdge(5, 8);
keypad.addEdge(6, 9);
keypad.addEdge(7, 8);
keypad.addEdge(7, "*");
keypad.addEdge(8, 0);
keypad.addEdge(8, 9);
keypad.addEdge(9, "#");
keypad.addEdge("*", 0);
keypad.addEdge(0, "#");

console.log(keypad.adjacencyList);

console.log(solution([1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5], "right"));
//"LRLLLRLLRRL"
console.log(solution([7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2], "left"));
// "LRLLRRLLLRR"
console.log(solution([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], "right"));
// "LLRLLRLLRL"