⏳최소 요소 제거 게임(minimumNumberGame)

기본 정보

#스파르타코딩클럽 #내일배움캠프(프론트엔드_React) #35일/94일

#알고리즘(탐험반) #week3

학습일: 2024. 6. 4.(화)

---

배운 내용 요약

1. 자바스크립트 전역함수 Infinity

절대 답(예: 최소값)이 될 수 없는 수로 대체하는 방법을 새로 배웠다.

    Alice = nums[minIndex];
    nums[minIndex] = Infinity;

 

2. While문의 조건 활용

빈 배열인 arr의 길이가 nums의 길이와 같아지면 반복문은 끝난다는 것을 이번에 새로 배웠다.

 while (arr.length < nums.length) {...}

 

3. 배열의 자리(index)를 변수로 활용

• 배열의 최소값을 찾는 함수(for문)를 재사용할 수 있었다.(예: Alice 찾기, Bob 찾기)
• 정답(Alice, Bob)과 기존 배열(nums)의 훼손 없이 배열의 최소값 자리를 infinity로 대체하지만 사용할 수 있었다.

function minimumNumberGame(nums) {
  let arr = [];
  let minIndex = 0;
  let Alice = 0;
  ....
  arr.push(nums[minIndex]);
    arr.push(Alice); 
    nums[minIndex] = Infinity;
  }
  return arr;
}

 

---

문제 1. 최소 요소 제거 게임(minimumNumberGame)

// 문제 정의:

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

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

// sort, Math.min, indexOf 함수를 사용하지 마세요.
// (구두로 설명한 조건: while문 사용할 것)

// 예시:

// 입력: [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)

• while문 조건 - nums배열이 비워질 때까지
• 배열 nums에서 가장 작은 수 찾기 - 변수명: Alice
• 배열 nums에서 가장  작은 수의 index 찾기 - 변수명: minIndex
• 배열 nums에서 가장 작은 수의 자리를 무한대(Infinity)로 대체하기 (전역함수 Infinity === 절대 최소값이 될 수 없는 수)
• Infinity가 포함된 배열 nums에서 가장 작은 수(=Bob), 그 수의 index 각각 찾기
• Infinity가 포함된 배열 nums의 가장 작은 수를 무한대(Infinity)로 대체하기
• 결과배열 arr에 Bob과 Alice 차례로 push
• 결과배열 arr 반환

// 함수 구현:
function minimumNumberGame(nums) {
  let arr = [];
  let minIndex = 0;
  let Alice = 0;
  // Alice 찾기
  while (arr.length < nums.length) {
    for (let i = 0; i < nums.length; i++) {
      if (nums[i] < nums[minIndex]) {
        minIndex = i;
      }
    }
    Alice = nums[minIndex]; // 최소값(=Alice) 찾았다.!
    nums[minIndex] = Infinity; // 절대 최소값이 될 수 없는 수(=Infinity)로 최소값(=Alice)의 자리를 대체해!
    //Bob 찾기
    for (let i = 0; i < nums.length; i++) {
      if (nums[i] < nums[minIndex]) {
        minIndex = i;
      }
    }
    arr.push(nums[minIndex]); // 두번째 최소값(=Bob) 찾았고, 바로 결과배열 arr에 push! (두번째 최소값을 담을 변수 필요 없는 이유!)
    arr.push(Alice); // 첫번째 최소값(=Alice) 찾았고, 바로 결과배열 arr에 push!
    nums[minIndex] = Infinity; // 절대 최소값이 될 수 없는 수(=Infinity)로 두번째 최소값(=Bob)의 자리를 대체해!
  }
  return arr;
}

 

다른 풀이방법 by Nicholas teacher

function minimumNumberGame(nums) {
  let arr = [];
  let [alice, bob] = [0,1];
  while(arr.length < nums.length) {
      [alice, bob] = [0,1];
      for(let i=0; i < nums.length; i++) {
          if(nums[i] < nums[alice]) {
              bob = alice;
              alice = i;
          }
          if(nums[i] < nums[bob] && i != alice) {
              bob = i;
          }
      }
      arr.push(nums[bob]);
      arr.push(nums[alice]);
      nums[alice] = Infinity;
      nums[bob] = Infinity;
  }
  return arr;
}