때로는 소프트웨어 엔지니어로서 기술 면접에서 직면할 수 있는 가장 어려운 질문이 언뜻 보기에는 간단해 보이는 질문입니다.

종종 단순해 보이는 배열이나 문자열 알고리즘을 작성하는 것은 우리가 일을 지나치게 복잡하게 하거나 단순히 그러한 데이터 유형으로 작업하는 더 기본적인 빌딩 블록 중 일부를 알지 못하기 때문에 우리를 함정에 빠뜨릴 것입니다.

이것을 완벽하게 구현하는 질문은 배열 회전입니다.

프롬프트

숫자 배열(숫자)과 해당 배열을 오른쪽으로 몇 번이나 "회전"해야 하는지(k)에 대한 정수가 주어졌다고 가정해 보겠습니다.

이것은 무엇을 의미 하는가? 시각화해 보겠습니다.

nums = [1, 2, 3, 4, 5]

k = 3
=> [3, 4, 5, 1, 2]

k = 2
=> [4, 5, 1, 2, 3]

k = 1
=> [5, 1, 2, 3, 4]

보시다시피, 배열을 "회전"한다는 것은 단순히 해당 값을 오른쪽(또는 왼쪽)으로 이동하고 회전 목마를 회전하는 것과 같이 배열의 반대쪽 끝에 다시 놓는 것입니다.

이제 어떻게 하면 될까요?

솔루션

인터뷰 환경에서 이 질문을 설득력 있게 만드는 이유는 이 질문을 해결할 수 있는 여러 가지 방법이 있다는 것입니다. 이 모든 방법은 런타임과 공간 복잡성에 서로 다른 영향을 미칩니다. 모든 사람이 다르게 할 수 있으므로 후보자가 "단순한"문제를 해결하고 설명하는 다양한 방법을 보는 것은 좋은 질문입니다.

오늘 우리는 두 가지 잠재적인 솔루션을 살펴볼 것입니다.

.pop() 및 .unshift() 배열 메서드를 사용하는 "무차별 대입"접근 방식.

배열 반전을 사용하는 보다 복잡한 솔루션입니다.

먼저 코드를 살펴본 다음 코드에서 무슨 일이 일어나고 있는지 분석해 보겠습니다.

1. 브루트 포스

const rotateArray1 = function(nums, k) {

  for (let i = 0; i < k; i++) {
      nums.unshift(nums.pop());
  }

  return nums;
}

이것은 "무차별 대입"접근 방식으로 간주됩니다. 본질적으로 처음에 문제에 대해 생각할 수 있는 가장 직접적인 방법이기 때문입니다.

우리는 배열의 끝에서 무언가를 제거한 다음 앞쪽에 놓기를 원한다는 것을 알고 있습니다. 그리고 우리는 그것을 (k)번 하고 싶어한다는 것을 압니다. 맞죠?

이 솔루션은 정확한 방향을 코드에 넣습니다. 배열의 마지막 요소를 pop()할 때마다 for 루프를 (k)번 실행하고 그것을 배열의 앞쪽으로 unshift()에 대한 인수로 제공합니다. 그런 다음 끝에 배열을 반환합니다.

여기서 런타임 복잡도는 O(n * k)입니다. 왜냐하면 우리가 unshift()를 사용할 때마다 JavaScript는 후드 아래 배열의 각 요소를 다시 배치하기 때문입니다.

공간 복잡도는 원래 배열을 제자리에서 수정하기 때문에 O(1) 또는 상수 공간입니다. 엄청난!

2. 반전

const rotateArray2 = function(nums, k) {

  // reverse helper function
  function reverse(arr, start, end) {
    while (start < end) {
      [arr[start], arr[end]] = [arr[end], arr[start]];
      start++;
      end--;
    }
  }

  k %= nums.length;

  reverse(nums, 0, (nums.length - 1));
  reverse(nums, 0, (k - 1));
  reverse(nums, k, (nums.length - 1));

  return nums;
}

이것은 지금까지 세 가지 솔루션 중 가장 흥미로운 솔루션입니다. 이것은 당신이 처음에는 생각하지 않았을 것 같은 일종의 알고리즘 솔루션이지만 잠시 동안 "더 큰 그림"에 대해 생각한 후에 올 수 있습니다.

회전 중인 배열을 시각화하면 다음과 같은 패턴을 확인할 수 있습니다.

nums = [1, 2, 3, 4, 5]

k = 2
=> [4, 5, 1, 2, 3]

// original array reversed
[5, 4, 3, 2, 1]

// reverse just the first (k) elements
[4, 5, 3, 2, 1]

// see where we're going?

// reverse from (k) to the end
[4, 5, 1, 2, 3]

그리고 당신은 회전된 결과를 얻었습니다!

다시 말하지만, 이것은 처음에는 생각할 수 없는 약간의 논리 비약이지만 이 문제에 대해 설정한 범위 내에서 완벽하게 작동합니다.

실제 솔루션의 경우, 배열, 시작 인덱스 및 끝 인덱스를 취하는 도우미 함수를 설정한 다음 ES6 구문을 사용하여 증가하기 전에 array[start] 및 array[end] 요소를 교환합니다. 및 포인터 감소.

위의 예를 기반으로 이 함수를 세 번 호출해야 한다는 것을 알고 있습니다.

한 번은 전체 배열을 뒤집습니다.

nums[0]에서 k로 반전하려면 한 번.

한 번은 k에서 끝까지 뒤집습니다.

그리고 우리는 끝났습니다!

여기서 런타임 복잡도는 O(n * 3)입니다. 왜냐하면 여전히 각 요소를 적어도 한 번은 뒤집을 필요가 있기 때문입니다. 우리는 이것을 세 번 반복할 것입니다.

여기서 공간 복잡도는 다시 상수 O(1)입니다. 여전히 훌륭합니다!


당신은 그것을 가지고 있습니다! 동일한 문제에 대해 완전히 다르지만 똑같이 실행 가능한 두 가지 솔루션입니다. 두 가지를 모두 아는 것의 장점은 도구 상자에 더 많은 잠재적 도구가 있고 면접관이 다른 접근 방식을 시도하도록 요청할 경우 다른 방식으로 문제에 대답할 수 있다는 것입니다.

재미있게 읽으셨기를 바랍니다! :)