[Programmers] #120869 - 외계어 사전 [Java][C++][Python]

문제 링크

---

1. 아이디어

spell의 알파벳을 한번씩만 모두 사용해서 만든 단어가 dic에 존재하는지 판단하는 문제로 애너그램 여부를 판단하는 간단한 문제다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \log N + D \times L \log L)$	$O(N)$

($N$ = spell의 글자 수, $D$ = dic의 단어 수, $L$ = dic 단어의 최대 길이. Java는 정렬 없이 크기 26 개수 배열로 판정해 시간 $O(D \times (N + L))$, Python은 spell을 제자리 정렬한 뒤 단어별 정렬 사본만 유지해 공간 $O(L)$)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(String[] spell, String[] dic) {
        String word = String.join("", spell);
        for (String s : dic) {
            if (isAnagram(word, s)) return 1;
        }

        return 2;
    }

    static boolean isAnagram(String s1, String s2) {
        int[] cnt = new int[26];
        for (char c : s1.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : s2.toCharArray()) {
            cnt[c - 'a']--;
        }

        for (int x : cnt) {
            if (x != 0) return false;
        }

        return true;
    }
}

spell의 알파벳을 이어 붙인 문자열 word를 만든 후, 알파벳 소문자에 대한 카운팅 배열을 통해 애너그램 여부를 판단하는 isAnagram 메서드를 활용했다.

#include <bits/stdc++.h>
using namespace std;

int solution(vector<string> spell, vector<string> dic) {
    string word;
    for (string& s : spell) word += s;
    sort(word.begin(), word.end());

    for (string& s : dic) {
        sort(s.begin(), s.end());
        if (word == s) return 1;
    }

    return 2;
}

spell의 알파벳을 이어 붙인 문자열 word를 만들고 정렬을 수행했고, 이후 dic의 각 단어를 정렬하여 일치하는지 비교했다.

def solution(spell, dic):
    spell.sort()

    for s in dic:
        if spell == sorted(s):
            return 1

    return 2

spell을 정렬한 후 dic의 각 단어를 sorted로 정렬하여 반환된 리스트를 통해 일치하는지 비교했다.

---