프로그래머스 외계어 사전

문제 설명

PROGRAMMERS-962 행성에 불시착한 우주비행사 머쓱이는 외계행성의 언어를 공부하려고 합니다. 알파벳이 담긴 배열 spell과 외계어 사전 dic이 매개변수로 주어집니다. spell에 담긴 알파벳을 한번씩만 모두 사용한 단어가 dic에 존재한다면 1, 존재하지 않는다면 2를 return하도록 solution 함수를 완성해주세요.

---

제한사항

• spell과 dic의 원소는 알파벳 소문자로만 이루어져있습니다.
• 2 ≤ spell의 크기 ≤ 10
• spell의 원소의 길이는 1입니다.
• 1 ≤ dic의 크기 ≤ 10
• 1 ≤ dic의 원소의 길이 ≤ 10
• spell의 원소를 모두 사용해 단어를 만들어야 합니다.
• spell의 원소를 모두 사용해 만들 수 있는 단어는 dic에 두 개 이상 존재하지 않습니다.
• dic과 spell 모두 중복된 원소를 갖지 않습니다.

---

입출력 예

spell dic result

["p", "o", "s"]	["sod", "eocd", "qixm", "adio", "soo"]	2
["z", "d", "x"]	["def", "dww", "dzx", "loveaw"]	1
["s", "o", "m", "d"]	["moos", "dzx", "smm", "sunmmo", "som"]	2

---

문제를 처음보고 이게 왜 레벨 0인지 의문이 들 정도의 레벨이였다.

C++ STL 알고리즘의 조합을 사용안하고 푸는 방법도 있겠지만 코드가 길어질 것 같아

아래와 같이 풀었다.

글자를 조합해서 모든 경우의 단어를 배열에 담아주고, 기존 사전과 비교하며 찾는 방식을 떠올려보았다.

 

알고리즘

1. 조합을 구하기 위해 next_permutation을 사용한다.
2. word라는 변수에 문자하나씩 더해가며 모든 조합을 찾는다.
3. 조합을 찾음과 동시에 words 백터에 단어를 넣어준다.
4. 추후에 dic백터와 words백터를 하나식 비교해나가며 찾는경우 바로 1을 반환해주는 방식이다.

 

코드1

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<string> spell, vector<string> dic) {
    int answer = 0;
    string word=" ";
    vector<string>words;
    
    sort(spell.begin(), spell.end());   
    
    do{
        for(int i=0; i<spell.size();i++){
            word+=spell[i];
        }
        words.push_back(word);
        word="";
    }while(next_permutation(spell.begin(),spell.end()));
        
    
    for(int i=0; i<dic.size();i++){
        for(int j=0;j<words.size();j++){
            if(dic[i]==words[j]){
                answer++;
                break;
            }
        }
    }
    return (answer > 0) ? 1 : 2;
}

이렇게 코드를 작성하면 6번에서 틀렸다고 뜬다.

 

코드2

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<string> spell, vector<string> dic) {
    // 문자열이 존재하는지 여부를 나타내는 변수
    bool found = false;
    string word;
    vector<string> array = spell;
    vector<string> words;

    sort(array.begin(), array.end());

    do {
        word = "";
        for (int i = 0; i < array.size(); i++) {
            word += array[i];
        }
        words.push_back(word);
    } while (next_permutation(array.begin(), array.end()));

    // dic 벡터의 각 요소와 words 벡터의 각 요소를 비교하여 일치하는지 확인
    for (int i = 0; i < dic.size(); i++) {
        for (int j = 0; j < words.size(); j++) {
            if (dic[i] == words[j]) {
                found = true;
                break;
            }
        }
        if (found) {
            break;
        }
    }

    // 문자열이 존재하는 경우 1을 반환하고, 그렇지 않으면 2를 반환
    if (found) {
        return 1;
    } else {
        return 2;
    }
}