펌웨어 롤백 후보

문제

IoT 기기 관리 서버는 배포 이력에 남아 있는 펌웨어 버전 문자열 목록을 관리합니다. 현재 버전 current에서 문제가 발견되면, 현재 버전보다 낮은 버전 중 가장 높은 것부터 차례로 롤백 후보를 제시해야 합니다.

버전 문자열은 다음 형식입니다.

<코어>            예: "2.10.3", "1.0", "10"
<코어>-<프리릴리스>  예: "2.10.3-beta.2", "1.0.0-rc.1.hotfix"

• 코어 는 .로 구분된 숫자 세그먼트 1~4개입니다.
• 프리릴리스 는 - 뒤에 .로 구분된 식별자 1~4개이며, 각 식별자는 숫자로만 이루어졌거나 소문자 알파벳으로만 이루어져 있습니다.

두 버전의 우선순위(높고 낮음)는 아래 규칙으로 비교합니다.

1. 코어 비교 — 세그먼트를 앞에서부터 수치 로 비교합니다 (1.9 < 1.10, 1.02.3 = 1.2.3). 세그먼트 개수가 다르면 부족한 쪽을 0으로 채워 비교합니다 (1.0 = 1.0.0, 1.0 < 1.0.0.1).
2. 프리릴리스 유무 — 코어가 같을 때, 프리릴리스가 붙은 버전은 정식(프리릴리스 없는) 버전보다 낮습니다 (2.0.0-rc.1 < 2.0.0).
3. 프리릴리스 식별자 비교 — 둘 다 프리릴리스가 있으면 식별자를 앞에서부터 하나씩 비교합니다.
   • 둘 다 숫자면 수치 비교 (beta.2 < beta.11)
   • 둘 다 알파벳이면 사전순 비교 (alpha < beta)
   • 숫자 식별자는 알파벳 식별자보다 낮습니다 (alpha.1 < alpha.beta)
   • 앞부분이 전부 같고 한쪽 식별자가 더 적으면, 적은 쪽이 낮습니다 (alpha < alpha.1)

solution(versions, current, k)은 versions 중 current보다 엄격히 낮은 버전만 골라 높은 것부터 내림차순 으로 정렬한 뒤 앞에서 k개를 반환합니다.

• 우선순위가 같은 버전들끼리는 versions에 먼저 등장한 것이 앞에 옵니다 (안정 정렬). 표기가 달라도 규칙상 같으면(예: 1.0과 1.0.0) 같은 버전입니다.
• 후보가 k개 미만이면 있는 만큼만 반환합니다.
• 반환하는 문자열은 입력에 있던 표기 그대로여야 합니다.

예시

• 예시 1: 1.10.0은 1.9.3보다 높습니다(둘째 세그먼트 10 > 9). 2.0.0은 현재 버전과 같아 제외됩니다.
• 예시 2: 프리릴리스 규칙에 따라 rc.1 > beta.11 > beta.2 > alpha.beta > alpha.1 > alpha 순입니다.
• 예시 3: 1.0, 1.0.0, 1은 모두 같은 버전이므로 입력 순서를 유지합니다.

제약 조건

• 1 ≤ versions.length ≤ 10,000
• 1 ≤ k ≤ 10,000
• 각 버전 문자열 길이는 30 이하이며, 위에서 정의한 형식을 항상 만족합니다.
• 코어의 각 숫자 세그먼트는 0 이상 1,000,000 이하입니다 (선행 0이 있을 수 있음).
• current도 같은 형식의 버전 문자열입니다 (versions에 없을 수도 있음).
• 같은 버전 문자열이 여러 번 등장할 수 있습니다.

시간 복잡도 목표: O(n log n × L) (L = 버전 문자열 최대 길이)