[TIL] 8주차 화요일. 알고리즘 탐험반 문제

문제

문제 정의:

nums 배열이 주어졌을 때, 앨리스와 밥이 게임을 합니다. 매 라운드마다 앨리스는 nums에서 최소 요소를 제거하고, 그 다음 밥이 같은 작업을 합니다.
밥은 제거한 요소를 결과 배열 arr에 추가하고, 그 다음 앨리스가 제거한 요소를 추가합니다. 이 과정을 nums가 비워질 때까지 반복합니다.
최종적으로 결과 배열 arr을 반환하세요.

다음의 조건을 만족해야 합니다:

sort, Math.min, indexOf 함수를 사용하지 마세요.

예시:

입력: [5, 4, 2, 3]
출력: [3, 2, 5, 4]

설명:
첫 번째 라운드에서는 앨리스가 2를 제거하고, 밥이 3을 제거합니다. 밥이 먼저 3을 arr에 추가하고, 앨리스가 2를 추가합니다.
arr = [3, 2]가 됩니다. 두 번째 라운드에서는 앨리스가 4를 제거하고, 밥이 5를 제거합니다.
결과적으로 arr = [3, 2, 5, 4]가 됩니다.

입력: [2, 5]
출력: [5, 2]

설명:
첫 번째 라운드에서는 앨리스가 2를 제거하고, 밥이 5를 제거합니다. 밥이 먼저 5를 arr에 추가하고, 앨리스가 2를 추가합니다.
결과적으로 arr = [5, 2]가 됩니다.

과정 1.

1) 저장할 새 배열 = arr[]
2) while (i < nums.length - 1) {}
3) if 첫번째가 두번째보다 크면 -> 첫번째랑 세번째랑 비교
4) else 두번째랑 세번째를 비교
5) arr에 num 추가
6) 똑같이 반복해서 arr[0]에 두번째 결과 추가
이런 식으로 로직을 생각해보고 시작했다.

function minimumNumberGame(nums) {
  let arr = [];
  let i = 0;
  let num = 0;
  while (i < nums.length - 1) {
    if (nums[i] < nums[i + 1]) {
      num = nums[i];
    } else {
      num = nums[i + 1];
    }
    i++;
  }
}

이렇게 첫 단계를 시작해봤는데 이러면 마지막에 num = nums[nums.length-1] 이렇게 되는 문제가 있긴 때문에... 다시 생각하기 시작했다.

과정 2.

ai의 도움을 사용해서.... ㅋㅋㅋㅋ 써보니 내가 너무 복잡하게 생각했다는 걸 알게 되었다.
그냥 다음값이 현재값(min)보다 작으면 다음값을 min에 넣으면 되는 거였어. else를 쓸 필요가 없었던 거야. 내가 처음에 작성했던 else는 이미 기본 전제니까.
바보 같은 부분에서 시간을 엄청 허비했다.

function minimumNumberGame(nums) {
  let arr = [];
  let min = nums[0];
  let i = 1;
  while (i < nums.length) {
    if (nums[i] < min) {
      min = nums[i];
    }
    i++;
  }
  return(min);
}

과정 3.

문제의 조건을 지키면서, 작은 숫자부터 계속 찾아서 새 배열에 붙이는 로직은 구현했다.
filter 사용.

function minimumNumberGame(nums) {
  let arr = [];
  while (nums.length > 0) {
    let min = nums[0];
    let i = 1;
    while (i < nums.length) {
      if (nums[i] < min) {
        min = nums[i];
      }
      i++;
    }
    arr.push(min);
    nums = nums.filter((num) => num !== min);
  }
  console.log(arr); // [ 1, 3, 4, 5, 6, 7 ]
}

minimumNumberGame([7, 4, 6, 1, 5, 3]);

과정 4.

순서를 조정하기 위해 isAliceTurn 변수를 추가했다.

function minimumNumberGame(nums) {
  let arr = [];
  let isAliceTurn = true;
  while (nums.length > 0) {
    let min = nums[0];
    let i = 1;
    while (i < nums.length) {
      if (nums[i] < min) {
        min = nums[i];
      }
      i++;
    }
    nums = nums.filter((num) => num !== min);
    if (isAliceTurn) {
      arr.push(min);
    } else {
      arr.splice(arr.length - 1, 0, min);
    }
    isAliceTurn = !isAliceTurn;
  }
  return arr;
}

과정 5.

아... 중복 항목은 없다고 생각했는데 테스트 코드를 돌려보니 중복도 고려해야 됐음. 다시...
그래서 최종!

function minimumNumberGame(nums) {
  // 초기값 세팅. 턴 구분을 위해 isAliceTurn 변수 추가.
  let result = [];
  let isAliceTurn = true;

  // if (nums의 길이가 0, 1일 경우) {result=nums}
  if (nums.length < 2) {
    result = nums;

    // else {nums의 길이가 0이 되기 전까지 계속 최소값을 하나씩 제거해줌}
  } else {
    while (nums.length > 0) {
      // 0번째 인덱스부터 하나씩 비교해서 작은 값을 min에 저장
      let minIndex = 0;
      for (let i = 1; i < nums.length; i++) {
        if (nums[i] < nums[minIndex]) {
          minIndex = i;
        }
      }
      let min = nums[minIndex];
      nums.splice(minIndex, 1);
      // 밥이 먼저 추가해야 하기 때문에
      // isAliceTurn이 true면 뒤에 추가, false면 뒤에서 두번째 인덱스에 추가
      // 다음 사람 턴으로 체인지 => isAliceTurn을 현재값의 반대로 바꿔주기
      if (isAliceTurn) {
        result.push(min);
      } else {
        result.splice(result.length - 1, 0, min);
      }
      isAliceTurn = !isAliceTurn;
    }
  }
  return result;
}