[LeetCode] 1122. Relative Sort Array

https://leetcode.com/problems/relative-sort-array/description/

leetcode - Relative Sort Array

문제 유형 : 정렬, 해시

문제 난이도 : Easy

 

문제

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.

두 정수 arr1과 arr2가 있다.

arr2의 요소는 하나씩만 있고, arr2의 모든 요소는 arr1에 있다.

arr1을 arr2의 순서대로 정렬하시오. arr2에 없는 숫자들은 맨 뒤로 보내서 오름차순으로 정렬하시오.

 

풀이

arr2에 가중치를 부여한 값을 해시테이블에 저장한다.

arr을 정렬하는데, 정렬의 lambda함수로,

만약 두 수 a,b모두 arr2에 있다면, 가중치대로 정렬하고, 

둘 중 하나가 없다면, 없는 수를 뒤로 보낸다.

둘다 arr2에 없다면, 오름차순으로 정렬한다.

 

코드

C++

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> mp;
        
        for(int i = 0; i < arr2.size(); i++) {
            mp[arr2[i]] = i + 1;
        }

        sort(arr1.begin(), arr1.end(), [&mp](int a, int b) {
            if (mp.find(a) != mp.end() && mp.find(b) != mp.end()) {
                return mp[a] < mp[b];
            } else if (mp.find(a) != mp.end()) {
                return true;
            } else if (mp.find(b) != mp.end()) {
                return false; 
            } else {
                return a < b;
            }
        });

        return arr1;
    }
};