압축 점수 순위표 만들기
자바스크립트 코딩테스트 문제로 coordinate-compression 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
점수 배열 scores가 주어질 때, 서로 다른 점수만 오름차순으로 정렬했을 때의 인덱스를 각 점수의 새 순위로 사용하려고 합니다.
예를 들어 scores = [50, 20, 50, 80]이라면 서로 다른 점수는 [20, 50, 80]이고, 각각의 압축 순위는 0, 1, 2입니다. 따라서 원래 배열을 압축 순위로 바꾸면 [1, 0, 1, 2]가 됩니다.
각 점수를 그 압축 순위로 바꾼 결과 배열을 반환하는 compressScoreRanks 함수를 작성하세요.
제한사항
scores.length는1이상100,000이하입니다.- 각 점수는
-1,000,000,000이상1,000,000,000이하의 정수입니다. - 같은 점수는 같은 압축 순위를 가집니다.
- 더 작은 점수일수록 더 작은 압축 순위를 가집니다.
- 반환값은
scores와 길이가 같은 정수 배열입니다.
예시
- 입력:
scores = [50, 20, 50, 80]→ 출력:[1, 0, 1, 2] - 입력:
scores = [100, 100, 100]→ 출력:[0, 0, 0] - 입력:
scores = [-10, 0, 5, -10, 1000000]→ 출력:[0, 1, 2, 0, 3]
힌트
- 먼저 중복을 제거한 뒤 정렬하면 각 값의 압축 순위를 쉽게 만들 수 있습니다.
- 정렬된 서로 다른 값 배열을 순회하며
값 -> 순위형태의 매핑을 준비해 보세요. - 마지막에는 원래
scores를 다시 순회하며 매핑된 순위를 꺼내면 됩니다.
해설
이 문제의 핵심은 실제 점수 크기 대신 상대적인 순서만 남기는 것입니다. 이를 흔히 좌표 압축이라고 부릅니다.
풀이 흐름은 다음과 같습니다.
scores에서 서로 다른 값만 뽑습니다.- 그 값들을 오름차순으로 정렬합니다.
- 정렬된 배열에서 각 값의 위치를 압축 순위로 사용해
Map에 저장합니다. - 원래
scores를 다시 순회하면서 각 점수를 대응하는 순위로 바꿉니다.
예를 들어 scores = [3, 1, 2, 1, 3, 2]라면:
- 서로 다른 값은
[3, 1, 2] - 정렬하면
[1, 2, 3] - 순위 매핑은
1 -> 0,2 -> 1,3 -> 2 - 원래 배열에 다시 적용하면
[2, 0, 1, 0, 2, 1]
이 방식은 정렬 때문에 시간 복잡도가 O(n log n)이고, 매핑과 결과 생성은 O(n)입니다. 입력 크기가 커도 충분히 처리할 수 있습니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.