[알고리즘] 문자열 정렬 기준과 H-Index 경계

오늘은 프로그래머스 정렬 문제 두 개를 연달아 풀었다. 같은 정렬 분류 안에 있어도, 하나는 비교 기준을 직접 만들어야 했고 다른 하나는 정렬 뒤 처음 만나는 경계를 찾으면 되는 문제였다.

가장 큰 수 정렬 기준

가장 큰 수는 숫자를 그대로 크기순으로 놓으면 풀리지 않는다. 3과 30처럼 자릿수가 다른 값은 단순 내림차순보다 이어 붙인 결과를 비교해야 하기 때문이다.

이번 풀이에서는 모든 숫자를 문자열로 바꾼 뒤 b+a와 a+b를 비교하는 기준으로 정렬했다. 이렇게 두 문자열을 이어 붙여 비교하면 어떤 순서로 배치해야 최종 결과가 커지는지 바로 판단할 수 있다.

정렬이 끝난 뒤 맨 앞 값이 0이면 전체가 0으로만 구성된 경우라서 바로 0을 반환하도록 처리했다. 그 외에는 StringBuilder에 차례대로 붙여 최종 문자열을 만들었다.

문제 제한이 numbers 길이 최대 100000이라서 핵심 비용은 정렬이다. 문자열 비교 길이는 각 원소가 최대 1000이므로 길지 않아서 전체 시간 복잡도는 O(n log n)으로 볼 수 있다.

H-Index 경계 판별

H-Index는 정렬을 한 뒤 여기부터는 인용 수가 남은 논문 수 이상이 되는 첫 지점을 찾는 문제로 풀었다.

배열을 오름차순 정렬해 두면 i번째 논문에서 남은 논문 수는 citations.length - i가 된다. 그래서 citations[i] >= citations.length - i를 처음 만족하는 순간 그 값이 바로 가능한 H-Index가 된다.

이 방식의 장점은 후보 값을 여러 번 가정하지 않아도 된다는 점이다. 정렬이 끝난 뒤 한 번만 훑으면 되기 때문에 구현이 짧고 경계도 분명하다. 끝까지 조건을 만족하는 지점이 없으면 0을 반환하면 된다.

복잡도와 결과

두 문제 모두 정렬이 중심이라 기본 시간 복잡도는 O(n log n)이다. 추가 메모리는 가장 큰 수에서 문자열 배열과 결과 문자열을 만드는 데 들고, H-Index는 정렬 이후 선형 탐색만 추가된다.

제출 기록 기준으로 가장 큰 수는 85.08 ms, 132 MB, H-Index는 3.04 ms, 79.6 MB가 나왔다. 같은 정렬 문제라도 비교 함수를 직접 설계해야 하는지, 정렬된 배열에서 경계만 찾으면 되는지에 따라 풀이 포인트가 꽤 다르다는 걸 다시 확인했다.