[LeetCode] - 2418. Sort the People

 

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Sort the People" 문제입니다.

--> https://leetcode.com/problems/sort-the-people/description/

 

문제 : 

 

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.

For each index i, names[i] and heights[i] denote the name and height of the ith person.

Return names sorted in descending order by the people's heights.

---

Example 1 :

Input : names = ["Mary","John","Emma"], heights = [180,165,170]

Output : ["Mary","Emma","John"]

Explanation : Mary is the tallest, followed by Emma and John.

 

Example 2 :

Input : names = ["Alice","Bob","Bob"], heights = [155,185,150]

Output : ["Bob","Alice","Bob"]

Explanation : The first Bob is the tallest, followed by Alice and the second Bob.

 

Constraints :

• n == names.length == heights.length
• 1 <= n <= 10^3
• 1 <= names[i].length <= 20
• 1 <= heights[i] <= 10^5
• names[i] consists of lower and upper case English letters.
• All the values of heights are distinct.

---

이 문제는 주어진 이름 배열과 키 배열을 바탕으로, 사람들의 키를 내림차순으로 정렬하여 이름 배열을 반환합니다.

 

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        Map<Integer, String> peopleMap = new HashMap<>();

        Integer[] heightsInt = new Integer[heights.length];

        for (int i = 0; i < heights.length; i++) {
            heightsInt[i] = heights[i];
        }
        for (int i = 0; i < names.length; i++) {
            peopleMap.put(heightsInt[i], names[i]);
        }

        Arrays.sort(heightsInt, Collections.reverseOrder());

        String[] ans = new String[names.length];
        for (int i = 0; i < names.length; i++) {
            ans[i] = peopleMap.get(heightsInt[i]);
        }

    return ans;
    }
}

 

제가 쓴 코드는 지금 돌이켜보니 쓸데없이 뭔가 추가되었고 긴 거처럼 느껴집니다. 그때의 제가 쓴 코드를 설명해 보자면, 

1. 맵 및 Integer 배열 초기화:
   • peopleMap은 키와 이름을 매핑하기 위한 HashMap입니다.
   • heightsInt는 heights 배열을 Integer 객체 배열로 변환한 것입니다. 이는 내림차순 정렬을 위해 필요합니다.
2. heights 배열을 Integer 배열로 변환:
   • heights 배열의 각 값을 Integer 객체 배열인 heightsInt에 복사합니다.
3. 맵에 키와 이름 매핑:
   • 각 키와 이름을 peopleMap에 매핑합니다.
4. 키 배열 내림차순 정렬:
   • heightsInt 배열을 내림차순으로 정렬합니다.
5. 정렬된 이름 배열 생성:
   • 정렬된 키 배열 heightsInt를 사용하여 peopleMap에서 이름을 추출하고, 이를 ans 배열에 저장합니다.

끝. 시간 복잡도는 Arrays.sort() 함수 때문에 O(nlogn) 이 되겠습니다.

---

솔루션들을 훑어보니 제 코드보다 훨씬 효율적이고 정리정돈이 잘된 코드가 있어서 공유해 봅니다 : 

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Map<Integer, String> mapping = new HashMap<>();

        for (int i = 0; i < n; ++i) {
            mapping.put(heights[i], names[i]);
        }

        Arrays.sort(heights);
        for (int i = 0; i < n / 2; ++i) {
            int temp = heights[i];
            heights[i] = heights[n - 1 - i];
            heights[n - 1 - i] = temp;
        }

        for (int i = 0; i < n; ++i) {
            names[i] = mapping.get(heights[i]);
        }

        return names;
    }
}
// heir-of-god 유저의 코드

---

내 코드, 다른 사람 코드의 Runtime 비교