[코테 풀이] 외계어 사전

자료구조 코테 문제 한 개씩 차근차근 풀다보니
이젠 뭔가 문제를 보고 해석하는 시야가 넓어지고 있는 것 같다!
아쥬 뿌듯해

Q) 외계어 사전

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

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/120869

import java.util.*;

class Solution {
    static String[] arr;
    static boolean[] visited;

    static String[] given;
    static List<String> strList = new ArrayList<>();
    ;
    
    public int solution(String[] spell, String[] dic) {
        List<String> dictionary = new ArrayList<>(Arrays.asList(dic));
        given = spell;
        int answer = 0;
        arr = new String[spell.length];
        visited = new boolean[spell.length];
        recur(0);
        for(String w : strList){
            if(dictionary.contains(w)){
                answer = 1;
                break;
            }
            else{
                answer = 2;
            }
        }
        return answer;
}
    public static void recur(int r) {
        String res = "";
        if (r == given.length) {
            for (String s : arr) {
                res += s;
            }
            strList.add(res);
            res = "";
        } else {
            for (int i = 0; i < given.length; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    arr[r] = given[i];
                    recur(r + 1);
                    visited[i] = false;
                }
            }
        }
    }
}

바로 어제 풀었던 순열 문제!!
백트래킹으로 풀었다.

1) 일단 contains() 메소드를 쓰고 싶어서 주어진 dic 배열을 dictionary라는 이름의 list로 변환한다.

2) spell에 있는 string가 들어갈 수 있는 (조합을 형성할 수 있는) arr이라는 배열과 방문했는지의 여부를 알 수 있는 visit배열을 spell의 길이만큼 만들었다.

3) 그리고 recur이라는 메소드를 실행해서 온갖 조합을 만들고 res라는 list에 그 값을 다 저장한다.

4) 그리고 이제 res에 있는 요소가 dictionary에 있는지 확인해주고 있다면 1을, 없다면 2를 answer에 지정한다.