[Programmers] 입문) 특이한 정렬

특이한 정렬

문제 설명

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

---

제한사항

• 1 ≤ n ≤ 10,000
• 1 ≤ numlist의 원소 ≤ 10,000
• 1 ≤ numlist의 길이 ≤ 100
• numlist는 중복된 원소를 갖지 않습니다.

입출력 예

numlist	n	result
[1, 2, 3, 4, 5, 6]	4	[4, 5, 3, 6, 2, 1]
[10000, 20, 36, 47, 40, 6, 10, 7000]	30	[36, 40, 20, 47, 10, 6, 7000, 10000]
[0, 0, 0, 0]	0	[0, 0, 0, 0]
[6, 10, 2]	6	[6, 10, 2]
[3, 30, 34, 5, 9]	9	[9, 5, 3, 30, 34]
[1, 2, 3, 4, 5]	1	[1, 2, 3, 4, 5]
[3, 30, 34, 5, 9]	99999	[34, 30, 9, 5, 3]

 

입출력 예 설명

입출력 예 #1

4에서 가까운 순으로 [4, 5, 3, 6, 2, 1]을 return합니다.

3과 5는 거리가 같으므로 더 큰 5가 앞에 와야 합니다.

2와 6은 거리가 같으므로 더 큰 6이 앞에 와야 합니다.

입출력 예 #2

30에서 가까운 순으로 [36, 40, 20, 47, 10, 6, 7000, 10000]을 return합니다.
20과 40은 거리가 같으므로 더 큰 40이 앞에 와야 합니다.

 

---

이번 문제는 그냥 생각나는데로 작성해보았다.

 

1. 배열을 오름차순으로 나열한다.
2. 주어진 n이 들어가는 위치를 판단한다
3. 확인한 위치를 기준으로 좌우로 이동하며 차이가 더 작은 것을 순서대로 넣는다.

 

이때 실패하는 테스트 케이스 3이 있었다.

이에 대해 질문하기를 탐색해본 결과 n이 터무니 없이 큰 수인 경우 탐색 범위를 넘겨버리는 어이없는 실수를 하게 되었다.

 

이에 최종 수정한 코드는 다음과 같다.

using System;

public class Solution {
    public int[] solution(int[] numlist, int n) {
        int[] answer = new int[numlist.Length];
        
        Array.Sort(numlist);
        
        int position = 0;
        for (int distance = 999999; position < numlist.Length; position++) {
            int gap = Math.Abs(numlist[position] - n);
            
            if (gap == 0 || distance == gap) {
                answer[0] = numlist[position];
                break;
            }
            
            if (distance < gap) {
                answer[0] = numlist[--position];
                break;
            }
            
            if (distance > gap)
                distance = gap;
        }
        
        
        // 만약 n이 너무 큰 경우
        if (position == numlist.Length) {
            answer[0] = numlist[numlist.Length - 1];
            position--;
        }
        
        
        // 선택된 위치부터 좌우 탐색
        for (int k = 1, goRight = 1, goLeft = 1; k < numlist.Length; k++) {
            int rightPosition = position + goRight;
            int leftPosition = position - goLeft;
            
            // 오른쪽으로 갈수 없는 경우 왼쪽 원소만 넣기
            if (rightPosition > numlist.Length - 1) {
                answer[k] = numlist[leftPosition];
                goLeft++;
                continue;
            }
            
            // 왼쪽으로 갈수 없는 경우 오른쪽 원소만 넣기
            if (leftPosition < 0) {
                answer[k] = numlist[rightPosition];
                goRight++;
                continue;
            }
            
            int leftGap = n - numlist[leftPosition];
            int rightGap = numlist[rightPosition] - n;
            
            // 오른쪽이 더 크면 왼쪽 원소를 넣기
            if (rightGap > leftGap) {
                answer[k] = numlist[leftPosition];
                goLeft++;
            }
            // 왼쪽이 더 크면 오른쪽 원소를 넣기
            if (leftGap > rightGap) {
                answer[k] = numlist[rightPosition];
                goRight++;
            }
            // 양쪽이 크기가 같으면 오른쪽, 왼쪽순으로 넣기
            if (rightGap == leftGap) {
                answer[k] = numlist[rightPosition];
                k++;
                answer[k] = numlist[leftPosition];
                goRight++;
                goLeft++;
            }
        }
        
        
        return answer;
    }
}

 

다른 분들의 풀이 중에는 크게 3가지 풀이가 있었다.

1. OrderBy와 ThenByDescending를 활용한 풀이
2. 배열 원소를 하나하나 순차적으로 다른 원소들과 비교하기
3. Dictionary를 활용하여 key값을 거리로, value를 숫자로 사용하여 정렬하기

using System;
using System.Linq;

public class Solution
{
    public int[] solution(int[] numlist, int n)
    {
        int[] answer = new int[numlist.Length];
        answer = numlist.OrderBy(x => Math.Abs(n-x)).ThenByDescending(x=>x).ToArray();
        return answer;
    }
}

using System;

public class Solution {
    public int[] solution(int[] numlist, int n) {
        int[] answer = new int[] {};
        
        for(int i = 1; i < numlist.Length; ++i) {
            for(int j = 0; j < i + 1; ++j) {
                int diff = Math.Abs(numlist[i] - n);
                int diff2 = Math.Abs(numlist[j] - n);
                
                if( diff < diff2 ) {
                    int temp = numlist[j];
                    numlist[j] = numlist[i];
                    numlist[i] = temp;
                } else if( diff == diff2 ) {
                    if( numlist[i] > numlist[j] ) {
                        int temp = numlist[j];
                        numlist[j] = numlist[i];
                        numlist[i] = temp;
                    }
                }
            }
        }
        
        return numlist;
    }
}

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] numlist, int n)
    {
        List<(int, int)> list = new List<(int, int)>();
        foreach (var it in numlist)
        {
            list.Add((it, Math.Abs(it - n)));
        }

        list.Sort((v1, v2) =>
        {
            if (v1.Item2 == v2.Item2)
            {
                return -v1.Item1.CompareTo(v2.Item1);
            }

            return v1.Item2.CompareTo(v2.Item2);
        });

        List<int> answer = new List<int>();
        foreach (var it in list)
        {
            answer.Add(it.Item1);
        }

        return answer.ToArray();
    }
}