[프로그래머스] Lv0.특이한 정렬

문제 설명

 

풀기 전 생각

• 먼저 배열을 오름차순 정리를 한 뒤, 주어진 n 값과 가장 차이가 없는 값 (min)을 구하기
• min값을 배열 처음에 넣고 min값을 기준으로 오른쪽, 왼쪽 거리 비교해 나가기
• 오름차순이니깐 left, right 거리가 같으면 right를 우선 배치
• 왼쪽이나 오른쪽이 끝지점에 다다르면 반대편 나머지 값을 순차적으로 복사해 주기

class Solution {
    public int[] solution(int[] numlist, int n) {
        int[] answer = new int[numlist.length];
        int nearIndex = 0; // n값과 가장 가까운 값의 index
        int min = 10000;  // n값과 가장 가까운 값
        int k = 0; // 정답 배열에 넣기위한 변수

        Arrays.sort(numlist); // 오름차순 정리

        for(int i = 0; i < numlist.length;i++){ 
            if(min >= Math.abs(n-numlist[i])){  // 오름차순이니 차이가 같으면 뒤에 나온것이 우선 배치
                min = Math.abs(n-numlist[i]); 
                nearIndex = i; 
            }
        }
        answer[k++] = numlist[nearIndex]; // 가장 가까운 값 넣기

        int right = nearIndex + 1; // 오른쪽 진행
        int left = nearIndex - 1;  // 왼쪽 진행

        while(right < numlist.length && left >= 0){ // 끝지점에 다다를때 까지
            if(Math.abs(n-numlist[right]) <= Math.abs(n-numlist[left])){ // 왼쪽이 거리 더 크거나 같으면
                answer[k++] = numlist[right++]; // 복사 후 오른쪽 이동
            }else{
                answer[k++] = numlist[left--]; // 복사 후 왼쪽 이동
            }
        }

        if(right == numlist.length){ // 오른쪽이 끝지점이면
            while(left >= 0){  // 왼쪽 끝까지 복사
                answer[k++] = numlist[left--];
            }
        }else if (left < 0){  // 왼쪽이 끝지점이면
            while(right < numlist.length){ // 오른쪽 끝까지 복사
                answer[k++] = numlist[right++];
            }
        }
        return answer;
    }
}

---

모범 답안

class Solution {
    public int[] solution(int[] numlist, int n) {

        int size = numlist.length;
        for(int i=0; i<size-1; i++){ 
            for(int k=i+1; k<size; k++){
                int a = (numlist[i] - n) * (numlist[i] > n ? 1 : -1);
                int b = (numlist[k] - n) * (numlist[k] > n ? 1 : -1);
                if(a > b || (a == b && numlist[i] < numlist[k])){
                    int temp = numlist[i];
                    numlist[i] = numlist[k];
                    numlist[k] = temp;
                }

            }
        }
        return numlist;
    }
}

특이한 정렬이라도 정렬이니 정렬 알고리즘을 쓰면 되는 것이었다...
그리고 n값과 거리가 같으면 n값보다 큰지 작은지 확인 후 1이나 -1을 곱해주면 된다.
위 코드는 삽입 정렬을 사용한 것이다.

참고

정렬 정리해서 링크 올리기