코딩테스트 준비 - Minimum Number Game

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : LeetCode

• 문제 : Minimum Number Game

• 사용언어 : C#

• 난이도 : 최하

• 풀이시간 : 9m

• 유형 : 배열, 리스트

You are given a 0-indexed integer array nums of even length and there is also an empty array arr. Alice and Bob decided to play a game where in every round Alice and Bob will do one move. The rules of the game are as follows:

• Every round, first Alice will remove the minimum element from nums, and then Bob does the same.

• Now, first Bob will append the removed element in the array arr, and then Alice does the same.

• The game continues until nums becomes empty.

Return the resulting array arr.

Example 1:

Input: nums = [5,4,2,3]
Output: [3,2,5,4]
Explanation: In round one, first Alice removes 2 and then Bob removes 3. Then in arr firstly Bob appends 3 and then Alice appends 2. So arr = [3,2].
At the begining of round two, nums = [5,4]. Now, first Alice removes 4 and then Bob removes 5. Then both append in arr which becomes [3,2,5,4].

Example 2:

Input: nums = [2,5]
Output: [5,2]
Explanation: In round one, first Alice removes 2 and then Bob removes 5. Then in arr firstly Bob appends and then Alice appends. So arr = [5,2].

Constraints:

• 2 <= nums.length <= 100

• 1 <= nums[i] <= 100

• nums.length % 2 == 0

문제 풀이 접근

이 문제는, 앨리스와 밥의 카드를 순서대로 뽑고, 추가하는 순서는 밥, 앨리스 순서대로 추가하는 것이다.
쉽게 앞의 카드 두장 뽑고 다시 뒤에 추가하는 것으로 이해해서 풀었는데, 이게 정답이었다.

문제 풀이 플로우,
1. nums 를 List에 넣는다. 반환용 List도 하나 선언한다.
2. 앨리스가 가장 작은 수 카드를 뽑는다. 뽑힌 카드는 List에서 지운다.
3. 밥이 가장 작은 수 카드를 뽑는다. 뽑힌 카드는 List에서 지운다.
4. 뽑힌 수를 밥, 앨리스 순서대로 반환용 리스트에 넣는다.
5. 반복을 1번에 넣은 리스트가 빌때까지 반복한다.
6. 최종적으로 ret List를 Array로 치환하여 Return 한다.

정답 작성 코드 (C#)

public class Solution {
    public int[] NumberGame(int[] nums) {
        List<int> inList = new List<int>();
        List<int> retList = new List<int>();
        
        for(int i=0;i < nums.Length;++i)
        {
            inList.Add(nums[i]);
        }
        
        int aliceTurn = Int32.MaxValue;
        int bobTurn = Int32.MaxValue;
        
        while(inList.Count != 0)
        {
            aliceTurn = Int32.MaxValue;
            bobTurn = Int32.MaxValue;
            
            for(int i = 0; i < inList.Count; ++i)
            {
                if (aliceTurn > inList[i])
                {
                    aliceTurn = inList[i];
                }
            }
            
            inList.Remove(aliceTurn);
                    
            // 앨리스의 카드선택
            
            for(int i = 0; i < inList.Count; ++i)
            {
                if(bobTurn > inList[i])
                {
                    bobTurn = inList[i];
                }
            }
            
            inList.Remove(bobTurn);
            // 밥의 카드선택
            
            if(bobTurn != Int32.MaxValue)
            {
                retList.Add(bobTurn);
            }
            // 밥의 카드 추가
            
            if(aliceTurn != Int32.MaxValue)
            {
                retList.Add(aliceTurn);
            }
            // 앨리스의 카드 추가
        }
        
        var ret = retList.ToArray();
        return ret;
    }
}

코드 결과