프로그래머스 - 단어 변환 [자바]

• 문제 링크 : 단어 변환

코딩테스트 연습 - 단어 변환

 

정답(Solution)

 

1. 재귀를 사용한 풀이

import java.util.*;

class Solution {

    private List<Integer> iList = new ArrayList<>();

    public int solution(String begin, String target, String[] words) {

        boolean f = false;

        for(String str : words){
            if(target.equals(str)){
                f = true;
                break;
            }
        }

        if(f){
            boolean[] v = new boolean[words.length];
            dfs(begin, target, words, v, 0);
        }else{
            return 0;
        }

        int[] a =iList.stream().sorted().limit(1).mapToInt(Integer::intValue).toArray();
        return a[0];
    }

    private void dfs(String begin, String target, String[] words, boolean[] v, int sum){
        if(begin.equals(target)){
            iList.add(sum);
            return;
        }

        for(int i=0; i<words.length; i++){
            if(!v[i] && check(begin, words[i])){
                v[i] = true;
                dfs(words[i], target, words, v, sum + 1);
                v[i] = false;
            }
        }

    }

    private boolean check(String begin, String word){
        char[] a = begin.toCharArray();
        char[] b = word.toCharArray();

        int cnt = 0;
        for(int i=0; i<a.length; i++){
            if(a[i] != b[i]){
                cnt++;
            }
        }

        return cnt == 1 ? true : false;
    }
}

 

분석

• dfs문제이다.
• 변환시킬 수 있는 단어인지 체크하는 함수와 방문 여부를 체크하는 배열 v만 잘 정리해주면 된다.

 

2. Stack을 사용한 풀이

import java.util.*;

class Solution {
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        Arrays.sort(words);
        int num = Arrays.binarySearch(words, target);
        int len = words.length;
        
        if(num >= 0){
            
            Stack<String> stk = new Stack<>();
            stk.push(begin);
            boolean[] v = new boolean[len];
            
            while(!stk.isEmpty()){
                String str = stk.pop();
                
                for(int i=0; i<len; i++){
                    if(v[i]) continue;
                    if(target.equals(str)) return answer;
                    if(check(words[i], str)){
                        v[i] = true;
                        stk.push(words[i]);
                        answer++;
                        break;
                    }
                }
            }
            
            return answer;
        }else{
            return 0;
        }
    }
    
    private boolean check(String str1, String str2){
        
        int count = 0;
        
        for(int i=0; i<str1.length(); i++){
            if(str1.charAt(i) != str2.charAt(i)){
                count++;
            }
        }
        
        return count == 1 ? true : false;
    }
}

 

분석

• Stack을 활용하여 dfs방식으로 풀이하였다.
• 1개의 char만 다른지 확인하는 check 함수를 만들어서 변환 가능한지 체크하였다.