문제

실패한 풀이 설명

원래의 배열에서 가장 작은 횟수로 바꾼 수를 찾는 문제.

아주 골치아픈 문제다. 재귀로는 절대 풀 수 없다. 그렇다고 재귀가 아닌 반복문을 쓴다고 풀리는 것도 아니다.
위의 실패한 풀이 두 개 모두 시간초과로 실패했다.
swap을 하지 않고 풀어야 풀리는 문제인 것 같다.
심지어 이전에 솔루션이라고 올라온 풀이들도 현재는 통과하지 않았다.
문제가 더 엄격해 진 것 같다.
실패 2번 풀이는 왜 실패인지 아직도 잘 모르겠다. 반복문을 한 번만 도는데도 swap해 주는 곳에서 시간을 더 많이 쓰게 되는 것일까?
밑에 성공한 다른 풀이를 분석하여 이해해 보도록 하겠다.

실패한 풀이 1

function swaploop(arr, result) {
  if (arr === Array.from(Array(arr.length), (_, i) => i + 1)) return result;

  for (let i = 0; i < arr.length - 1; i++) {
    const originNum = i + 1;
    const swapNum = arr[i];

    const isSwap = () => originNum !== swapNum;
    const findIndex = () => arr.indexOf(originNum);
    const swapNums = (a, b) => {
      const temp = arr[a];
      arr[a] = arr[b];
      arr[b] = temp;
    };

    if (isSwap()) {
      swapNums(i, findIndex());
      result++;
    }
  }
  return swaploop(arr, result);
}

function minimumSwaps(arr) {
  let result = 0;

  return swaploop(arr, result);
}

실패한 풀이 2

function minimumSwaps(arr) {
  let result = 0;

  for (let i = 0; i < arr.length; i++) {
    const originNum = i + 1;
    const currnetNum = arr[i];

    const isSwap = () => originNum !== currnetNum;

    const findIndex = () => arr.indexOf(originNum);

    const swapNums = (a, b) => {
      const temp = arr[a];
      arr[a] = arr[b];
      arr[b] = temp;
    };

    if (isSwap()) {
      swapNums(i, findIndex());
      result++;
      console.log(arr, result);
    }
  }

  return result;
}

성공한 풀이 설명

이 풀이가 통과하는 결정적인 이유는 visited라는 방문한 index를 저장하는 배열을 만들어 반복문을 돌더라도 반복 횟수를 줄인다는 점인 것 같다.
visited는 처음에 빈 배열이므로 무조건 while문에 들어간다.
while문에 들어간 수는 true가 되어 while문 재진입을 막는다.
arr[j] - 1는 현재 숫자보다 1보다 작은 수인데, 이 수가 다시 j로 저장되면서 while문이 순환되게끔 한다.
이렇게 반복되면서 돌다가 visited가 true인 수가 또 들어오게 되면 반복문을 중지하고 count에 cycle - 1을 더해 준다.
cycle에 1을 빼고 더해 주는 이유는 처음에 while문으로 들어갔을 때 1이 올라가는 것을 빼주는 것 같다.

설명을 대충 적었지만 정확히 왜 이렇게 돌아야 하는지 이해가 가지 않아서 나중에 다시 풀어 봐야겠다.

성공한 풀이

function minimumSwaps(arr) {
  let count = 0;
  let visited = [];

  for (let i = 0; i < arr.length; i++) {
    let j = i;
    let cycle = 0;

    while (!visited[j]) {
      visited[j] = true;
      j = arr[j] - 1;
      cycle++;
    }

    if (cycle) count += cycle - 1;
  }

  return count;
}

참고자료

저작자표시

[HackerRank][Javascript] Array - Minimum Swaps 2

문제