[Level2] 22. 조이스틱, 카펫

in 코딩테스트 on 프로그래머스




93. 조이스틱

프로그래머스 

function solution(name) {
  let num;
  let cost = [];

  for (let i = 0; i < name.length; i++) {
    num = name[i].charCodeAt();
    cost[i] = num <= 77 ? num - 65 : 26 - (num - 65);
  }

  const toRight = (arr, index) => {
    let length = 0;
    while (arr[index] === 0) {
      length++;
      index = index < arr.length - 1 ? index + 1 : 0;
    }
    return [length, index];
  };

  const toLeft = (arr, index) => {
    let length = 0;
    while (arr[index] === 0) {
      length++;
      index = index > 0 ? index - 1 : arr.length - 1;
    }
    return [length, index];
  };

  let path = [...cost];
  path[0] = 0;
  let pathIdx = min = 0;

  while (path.some((value) => value !== 0)) {
    let [rightLen, rightIdx] = toRight(path, pathIdx);
    let [leftLen, leftIdx] = toLeft(path, pathIdx);

    min += leftLen < rightLen ? leftLen : rightLen;
    pathIdx = leftLen < rightLen ? leftIdx : rightIdx;
    path[pathIdx] = 0;
  }

  return min + cost.reduce((acc, val) => acc + val, 0);
}

console.log(solution("JAN"));
//23

이 문제 하나 푸는데 1시간 30분이 걸렷다….
그치만 이것도 완벽한 답은 아니다..
프로그래머스 테스트는 통과하는데, 11번 케이스는 막힌다.
그리디여서 순간의 최적해지만 전체의 최적해에는 맞지 않는 거라 프로그래머스에서 그냥 맞다고 인정해준 것 같다.
min을 찾기위해 left, right를 비교할 때, 두 개의 값이 같을 때 어디로 가게 하느냐의 문제다..
뭐지 다익스트라로 해야하나..?ㅠㅠㅠㅠ
dfs 방식으로 푸신 분도 많은데 이것도 똑같이 완벽한 해답은 못구한것 같다!



94. 카펫

프로그래머스 

function solution(brown, yellow) {
  let sum = brown + yellow;
  let arr = [];
  for (let i = 0; i ** 2 <= sum; i++) {
    if (sum % i === 0) arr.push([0, i]);
  }
  for (let key in arr) {
    arr[key][0] = sum / arr[key][1];
  }
  let answer = arr.filter((value) => {
    return (value[0] - 2) * (value[1] - 2) === yellow;
  });
  return answer[0];
}


문제를 푸는 건 쉬운데 이해가 너무 어려웠다..!
테스트케이스 좀 자세히 설명해줘라…!!



best 풀이

function solution(brown, red) {
    var answer = [];
    for (var i = 3; i <= (brown+red)/i; i++) {
        var x = Math.floor((brown+red)/i);
        if( (x-2)*(i-2)=== red) {
            break;
        }
    }

    return [x,i];
}