(C++) - LeetCode (easy) 953. Verifying an Alien Dictionary

https://leetcode.com/problems/verifying-an-alien-dictionary/description/

Verifying an Alien Dictionary - LeetCode

정렬 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. string vector인 sortedWords를 선언해줍니다.

2. 주어진 order 사전을 통해 우선순위를 저장해줍니다. 이는 scoreMap을 이용해 key는 문자, value는 점수를 저장합니다.

📔 풀이과정

sort함수 이용, 만든 cmp함수로 기준을 제시해 정렬해줍니다.

정렬기준은 다음과 같습니다.

1. a, b 문자열 중 적은 size의 문자열 크기를 minSize에 저장하고 그만큼 for문을 수행해 큰 점수 순으로 정렬해줍니다.

2. 만약 minSize만큼 문자열이 모두 같다면 이후 남은 문자열 끼리 substr해서 더 적은 size를 가진 문자열이 사전의 앞에 있으므로 이 순으로 정렬해줍니다.

3. substr size가 같다면 해당 substr의 첫 글자는 항상 다르기 때문에 둘 중 더 큰 점수를 가진 문자열 순으로 정렬합니다.

📔 정답출력

정렬된 sortedWords와 words를 비교해 모두 같다면 true 아니면 false를 반환합니다.

---

📕 Code

📔 C++

map<char, int> scoreMap;

bool cmp (string &a, string &b) {
    int minSize = min(a.size(), b.size());
    for(int i = 0; i < minSize; i++) {
        if(scoreMap[a[i]] == scoreMap[b[i]]) continue;
        return scoreMap[a[i]] > scoreMap[b[i]];
    }
    string aa = a.substr(minSize);
    string bb = b.substr(minSize);
    if(aa.size() == bb.size()){
        return scoreMap[aa[0]] > scoreMap[bb[0]];
    }
    return aa.size() < bb.size();
}

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        vector<string> sortedWords = words;
       
        for(int i = order.size() - 1, score = 1; i >= 0; i--, score++) {
            scoreMap[order[i]] = score;
        }
        sort(sortedWords.begin(), sortedWords.end(), cmp);
        for(int i = 0; i < sortedWords.size(); i++) {
            if(sortedWords[i] != words[i]) return false;
        }
        return true;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.