특이한 정렬

문제 설명

정수 n을 기준으로 n과 가까운 수부터 정렬하려고 합니다.
이때 n으로부터의 거리가 같다면 더 큰 수를 앞에 오도록 배치합니다.
정수가 담긴 배열 numlist와 정수 n이 주어질 때 numlist의 원소를 n으로부터
가까운 순서대로 정렬한 배열을 return하도록 solution 함수를 완성해주세요.

풀이

public class CustomProximitySorter
{
    public static int[] Solution(int[] numlist, int n)
    {
        Stack<int> sortedNums = new Stack<int>();
        Stack<int> stashedNums = new Stack<int>();

        foreach (int num in numlist)
        {
            if (sortedNums.Count <= 0)
            {
                sortedNums.Push(num);
                continue;
            }
                
            //num이 sortedNums의 마지막 숫자보다 앞에 있어야 하는지 확인
            while (TryPush(sortedNums.Peek(), num, n))
            {
                //앞에 있어야 한다면 기존에 sortedNums에 있던 숫자를 제거
                stashedNums.Push(sortedNums.Pop());
                
                if (sortedNums.Count <= 0)
                    break;
            }
            
            sortedNums.Push(num);

            while (stashedNums.Count > 0)
            {
                sortedNums.Push(stashedNums.Pop());
            }
        }


        int[] answer = sortedNums.Reverse().ToArray();
        return answer;
    }

    private static bool TryPush(int topOfStack, int valueToPush, int standard)
    {
        //두 숫자를 비교해 기준 숫자에서 뺀 절대값이 두번째 숫자가 더 크다면 해당 위치에서 숫자를 추가
        if (Math.Abs(topOfStack - standard) < Math.Abs(valueToPush - standard))
            return false;
        //만약 두 숫자가 같다면
        else if (Math.Abs(topOfStack - standard) == Math.Abs(valueToPush - standard))
        {
            //값을 비교해 두번째 숫자가 더 크다면 해당 위치에서 숫자를 추가
            if (topOfStack > valueToPush)
                return false;
        }
        
        return true;
    }
}

접근 방법

• 2개의 Stack을 사용해 해당 정렬을 구현하고자 함
• 각각의 숫자를 비교해 주어진 숫자 n과 가까운지 검사하고 입력하고자하는 숫자가 더 앞에 와야 한다면 기존에 있던 숫자를 stashedNums에 옮겨두고 sortedNums 스택에 해당 숫자를 Push함
• 이후 옮겨둔 숫자를 다시 sortedNums 스택에 Push함

정렬 여부 판단

• 해당 입력된 숫자가 기존에 Stack에 있던 숫자를 제거하고 추가해야하는지 여부를 판단하는 함수를 작성

    private static bool TryPush(int topOfStack, int valueToPush, int standard)
    {
        //두 숫자를 비교해 기준 숫자에서 뺀 절대값이 두번째 숫자가 더 크다면 해당 위치에서 숫자를 추가
        if (Math.Abs(topOfStack - standard) < Math.Abs(valueToPush - standard))
            return false;
        //만약 두 숫자가 같다면
        else if (Math.Abs(topOfStack - standard) == Math.Abs(valueToPush - standard))
        {
            //값을 비교해 두번째 숫자가 더 크다면 해당 위치에서 숫자를 추가
            if (topOfStack > valueToPush)
                return false;
        }
        
        return true;
    }

• 기준이 되는 숫자인 standard에서 뺀 절대값을 비교해 입력하고자 하는 숫자인 valueToPush의 계산 값이 더 크다면 topOfStack 뒤에 valueToPush를 추가해야하므로 false를 반환
• 크지 않고 값이 같지만 valueToPush의 크기가 작다면 topOfStack 뒤에 valueToPush를 추가해야하므로 false를 반환
• 그렇지 않은 경우에 대해서는 반복하여 기존에 sortedNums에 있던 숫자 중에서 valueToPush보다 뒤에 와야 하는 숫자를 이동

정렬 과정

			...
            
            sortedNums.Push(num);

            while (stashedNums.Count > 0)
            {
                sortedNums.Push(stashedNums.Pop());
            }
        }
        
		int[] answer = sortedNums.Reverse().ToArray();
        return answer;

• 입력하고자하는 숫자인 num보다 뒤에 있어야하는 숫자를 전부 stashedNums로 이동했으므로 num을 추가
• 이후 옮겨뒀던 stashedNums을 다시 sortedNums에 추가
• Stack은 후입 선출이므로 가장 마지막에 추가된 값이 0번 인덱스에 위치하므로 반대로 정렬된 상태임
  (n에 가까운 순서로 숫자를 입력했으므로)
  따라서 순서를 뒤집어 정답을 반환