[Java] 프로그래머스 | 120880 특이한 정렬

📝 TIL

- [프로그래머스] 120880 특이한 정렬

 

제한사항

1 ≤ n ≤ 10,000

1 ≤ numlist의 원소 ≤ 10,000

1 ≤ numlist의 길이 ≤ 100

numlist는 중복된 원소를 갖지 않습니다.

 

입출력 예

입력 #1

numlist [1, 2, 3, 4,5, 6]

n 4

 

출력 #1

[4, 5, 3, 6, 2, 1]

---

🦔 설계 및 시도

n을 기준으로 정렬하기 때문에 빼서 절댓값을 한 값을

정렬하면 될 거라고 생각을 했다

처음에 Map을 쓰려다가, 지난번에 Map은 중복값이 안되는 걸 공부했기에

Comparater의 조건을 넣는 구문을 활용하기로 했다.

 

절댓값 아이디어는 문제를 보자마자 바로 떠올랐는데

확실히 자바 문법이 아직 익숙하지 않아서 구현하는 과정이 오래걸렸다

 

또 문제에서 중요한 건 거리가 똑같을 경우에는 큰 수가 앞에 오도록 하는 것!

 

 

🔥 풀이에 사용된 개념

List.sort(Comparator)

- 리스트를 커스텀 기준으로 정렬할 때 사용

list.sort((i, j) -> {
    if(Math.abs(n-i)==Math.abs(n-j)) return j-i;  // 같은 거리면 큰 수 우선
    return Math.abs(n-i)-Math.abs(n-j);          // 거리 기준 오름차순
});

 

큰 값이 앞에 와야 하므로 j-i, 나머지는 그냥 오름차순!

 

💡 풀이 소스 코드

 

시간복잡도 : O(n log n)

- List.sort()는 TimSort(삽입정렬+병합정렬) 기반이므로 O(n log n)

공간복잡도 : O(n)

 

import java.util.*;
class Solution {
    public int[] solution(int[] numlist, int n) {
        int[] answer = new int[numlist.length];
        
        // 리스트 변환
        List<Integer> list = new ArrayList<>();
        for(int nl : numlist){
            list.add(nl);
        }
        
        // 절댓값 비교
        list.sort((i, j) -> {
                 if(Math.abs(n-i)==Math.abs(n-j)) return j-i;
                 return Math.abs(n-i)-Math.abs(n-j);
        });
        
        for(int i=0; i<list.size(); i++){
            answer[i]=list.get(i);
        }
        return answer;
    }
}

 

---

🚀 새로 배운 내용

- Comparator를 활용한 다중 조건 정렬 : 두 개 이상 조건을 정렬할 때 사용하

 

---

😺  느낀점

두 값을 같이 활용해야 할 때 Map을 바로 떠올리는 것보다 다른 방법은 뭐가 있을까 항상 고민해보자

 

 

*소스 코드는 다음 깃허브에 올라옵니다 - https://github.com/s0ooo0k/Algorithm_Study

GitHub - s0ooo0k/Algorithm_Study: Algorithm Study 문제 및 풀이