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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

풀이

글자가 하나씩 바뀐다고 한다. => 글자들이 이어져 있다 => bfs 문제라 생각하고 문제를 풀었다.

bfs를 할 때 가장 고민이었던것이 while문 안에를 어떻게 설계하냐였다.

처음 풀 때는 단어의 길이도 최대 10이고 words의 개수도 최대 50이여서 단순하게 생각하였다.

단어의 각 문자마다 'a'부터 'z'까지 변경하여 words 배열에 있는지 확인하고 있으면 que에 넣는 식으로 구현했다.

물론 이렇게 풀어서 통과하였다.

 

좀 더 나은 풀이가 있지 않을까 싶어 찾아보았고 다시 새롭게 풀 때는 다음과 같이 풀었다.

words 배열에 있는 단어와 현재 단어와 다른 문자의 개수가 몇개인지 찾고 1개면 que에 넣고 아니면 지나가는 식으로 구현했다.

 

코드

처음 풀이

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {        
        int answer = 0;
                
        Queue<Info> que = new LinkedList<>();
        boolean visited[] = new boolean [words.length];
        
        que.add(new Info(begin, 0));
        while(!que.isEmpty()){
            Info info = que.poll();
            String str = info.word;
                       

            if(str.equals(target)){
                answer = info.cnt;
                System.out.println(str + " "+info.cnt);
                break;
            }
            for(int i=0;i<begin.length();i++){
                str = info.word;
                for(char ch = 'a'; ch <= 'z'; ch++){
                    str = str.substring(0,i)+ch+str.substring(i+1);
                    for(int j=0;j<words.length;j++){
                        if(!visited[j]&&str.equals(words[j])){
                            visited[j] = true;
                            que.add(new Info(str, info.cnt+1));
                        }
                    }
                }
            }
        }
        
        return answer;
        
    }
    public class Info {
        String word;
        int cnt;
        
        public Info(String word, int cnt){
            this.word = word;
            this.cnt = cnt;
        }
    }
}

 

다시 푼 풀이

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {        
        int answer = 0;
                
        Queue<Integer> que = new LinkedList<>();
        int dist[] = new int [words.length];
        
        for (int i = 0; i < words.length; i++) {
            if (dist[i] == 0 && diff(begin, words[i]) ) {
                que.offer(i);
                dist[i] = 1;
            }
        }
        
        
        while(!que.isEmpty()){
            int idx = que.poll();
            String str = words[idx];
                       
            if(str.equals(target)){
                answer = dist[idx];
                break;
            }
            for(int i=0;i<words.length;i++){
                if(dist[i] == 0 && diff(str, words[i])){
                    que.add(i);
                    dist[i] = dist[idx]+1;
                }
            }
            
        }
        
        return answer;
        
    }
    public boolean diff(String word1, String word2){
        int cnt = 0;
        for(int i=0;i<word1.length();i++){
            if(word1.charAt(i)!=word2.charAt(i)){
                cnt++;
            }
        }
        return cnt == 1;
    }
}