[java] 자바 람다식 정렬

안녕하세요! 오늘은 백준이나 프로그래머스 코딩 테스트를 풀 때 문자열이나 배열을 다루다 보면 무조건 마주치는 "정렬(Sorting)"에 대한 꿀팁을 가져왔습니다.

최근 프로그래머스의 '전국 대회 선발 고사' 문제를 풀다가 엄청난 치트키를 배우게 되어서, 까먹지 않기 위해 기록을 남깁니다!

❓내가 마주한 문제의 장벽

문제를 풀다 보면 이런 상황이 자주 생깁니다.
"참석한 학생들의 번호(인덱스)를 정렬해야 하는데, 정렬 기준은 그 학생들의 '등수' 순서여야 한다!"
처음에는 저도 정직하게 등수만 따로 리스트에 모아서 Collections.sort()로 정렬한 뒤, 이 등수가 원래 몇 번 학생의 등수였는지 찾으려고 이중 for문을 돌려가며 역추적을 했습니다.
정답은 맞췄지만, 코드가 길어지고 이중 for문 때문에 마음이 불편했죠.

💡구원투수: Collections.sort()의 숨겨진 기능

기본적으로 자바에서 ArrayList를 정렬할 때는 아래처럼 씁니다.

Collections.sort(list); // 오름차순으로 알아서 정렬해줌!

하지만 자바는 "내가 원하는 특별한 기준으로 정렬할 수 있는 기능"을 열어두었습니다. 그게 바로 람다식을 이용한 custom 정렬입니다!오늘의 핵심 코드를 먼저 보시죠.

// attendees에는 학생 번호 [0, 1, 2, 4, 5] 가 들어있습니다.
Collections.sort(attendees, (a, b) -> rank[a] - rank[b]);

🛠️ 이 코드가 대체 어떻게 작동하는 건가요?

이 코드는 자바에게 "리스트 안의 알맹이 자체를 비교하지 말고, 내가 주는 공식으로 우열을 가려줘!" 라고 부탁하는 것입니다.
자바가 내부적으로 정렬을 하려고 리스트에서 두 학생 a와 b를 뽑아냅니다.
그리고 우리가 작성한 공식인 rank[a] - rank[b]를 계산하죠.
1. rank[a] - rank[b] 결과가 음수(-)이면: a의 등수가 숫자가 더 작다는 뜻이므로, a를 앞으로 보냅니다. (오름차순)
2. 결과가 양수(+)이면: b의 등수가 숫자가 더 작다는 뜻이므로, b를 앞으로 보냅니다.
이 과정을 거치고 나면, 놀랍게도 attendees 리스트 안에는 여전히 [학생 번호]가 들어있지만, 그 배치 순서는 [등수가 가장 높은 학생 번호] 순으로 완벽하게 재배치됩니다!

🚀 전과 후 코드 비교 (비포 & 애프터)

이중 for문으로 역추적하던 과거의 나:
// 등수 정렬하고... 다시 원본 rank 배열 뒤져가면서 인덱스 찾기 (복잡)

for(int i=0; i<3; i++){
    for(int j=0; j<rank.length; j++){
        if(list.get(i) == rank[j]){
            ans[i] = j;
        }
    }
}

람다식 정렬을 배운 오늘의 나:
// 단 한 줄로 등수 기준 학생 번호 정렬 끝!

Collections.sort(attendees, (a, b) -> rank[a] - rank[b]);

int studentA = attendees.get(0); // 등수 가장 높은 학생 번호
int studentB = attendees.get(1);
int studentC = attendees.get(2);

귀찮은 이중 for문과 역추적 과정이 통째로 날아가고 코드가 반의반으로 줄어들었습니다. 속도(시간 복잡도) 측면에서도 이중 for문($O(N^2)$)을 쓰는 것보다 자바 고유의 정렬 알고리즘($O(N \log N)$)을 쓰는 것이 비교도 안 될 정도로 빠릅니다.

앞으로 정렬 기준이 복잡한 2차원 배열이나 인덱스 매핑 문제를 만나면 무조건 이 람다식 정렬을 떠올려야겠습니다! 감사합니다~