프로그래머스 H-Index 풀이: 정렬 후 인용 수와 순위 비교
프로그래머스 H-Index에서 인용 횟수를 내림차순으로 정렬하고 현재 순위와 비교한다. 인용 횟수가 순위보다 작아지는 경계에서 H-Index를 구한다.
#정렬
원소를 조건에 맞는 순서로 배치해 탐색과 선택을 단순하게 만드는 풀이를 다룬다. 현재 1개의 풀이가 있다.
정렬 알고리즘 학습 가이드
필요한 주제만 펼쳐서 정렬의 기본 성질과 문제 조건에 맞는 정렬 선택 기준을 익힌다.
정렬 기본 개념
정렬은 데이터의 순서를 특정 기준에 맞게 재배치하는 과정이다. 오름차순·내림차순뿐 아니라 절댓값, 여러 필드, 우선순위 같은 비교 규칙도 정렬 기준이 될 수 있다.
- 오름차순: 작은 값에서 큰 값 순서
- 내림차순: 큰 값에서 작은 값 순서
- 비교 기준: 숫자, 문자열, 여러 필드 중 문제에서 요구한 기준
- 안정 정렬: 같은 키의 원래 순서를 유지하는 정렬
정렬 자체가 목적이 아니라, 이후의 이분 탐색·투 포인터·그리디 선택을 가능하게 하는 전처리로 쓰이는 경우가 많다.
정렬 후 문제를 단순화하는 패턴
정렬하면 원소 사이의 순서 관계가 명확해져 반복 비교나 후보 제거를 안전하게 수행할 수 있다.
| 정렬 뒤 조건 | 연결되는 방법 | 활용 예 |
|---|---|---|
| 양끝 합의 크기를 비교 | 투 포인터 | 두 수의 합, 구간 넓이 |
| 중간값 기준으로 후보 절반 제거 | 이분 탐색 | 정렬 배열 검색 |
| 현재 선택의 끝점 비교 | 그리디 | 구간 선택·회의실 배정 |
| 같은 값이나 구간을 묶음 | 선형 스캔·해시 | 중복 제거·빈도 그룹화 |
| 가장 작은 후보부터 처리 | 투 포인터·힙 | 두 리스트 병합 |
정렬 알고리즘 선택
| 상황 | 우선 고려할 방법 | 주의할 점 |
|---|---|---|
| 일반적인 배열 정렬 | 언어의 내장 정렬 | 비교 기준과 원본 변경 여부 확인 |
| 같은 키의 순서 보존 필요 | 안정 정렬 | 정렬 구현의 안정성 확인 |
| 연결 리스트 정렬 | 병합 정렬 | 노드 연결과 분할·병합 관리 |
| 값의 범위가 작고 정수만 존재 | 계수 정렬·기수 정렬 | 값 범위에 따른 메모리 사용 |
시간 복잡도와 구현 선택
비교 기반 정렬의 일반적인 하한은 `O(n log n)`이다. 코딩 테스트에서는 직접 정렬을 구현하기보다 내장 정렬의 복잡도와 원본 변경 여부를 확인하고 쓰는 것이 안전하다.
- 정렬 결과만 필요하면 `sort()`로 원본을 바꾸거나 `sorted()`로 복사본을 만들지 선택
- 여러 조건을 정렬할 때는 튜플 키나 명시적인 key 함수를 사용
- 정렬 뒤 원래 인덱스가 필요하면 `(값, 인덱스)` 쌍으로 저장
- 정렬이 필요하지 않은 해시·선형 스캔 풀이가 있는지 먼저 비교
자주 하는 실수
- 오름차순과 내림차순을 문제 조건과 반대로 선택하는 경우
- 정렬된 배열을 순회하면서 원본 인덱스를 잃는 경우
- 같은 키의 순서가 필요한데 불안정한 정렬이나 잘못된 보조 키를 사용하는 경우
- 문자열 숫자를 사전순으로 정렬해 실제 수의 크기와 달라지는 경우
- 정렬 후 투 포인터나 이분 탐색의 경계 조건을 다시 정의하지 않는 경우