[Java] 프로그래머스 - 단어 변환 (3단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

프로그래머스

 

 

 

 

 

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
    
    	//words에 target이 있는지 없는지 확인
        boolean value = false;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(target)) {
                value = true;
                break;
            }
        }
        if (!value) return 0;
        
        //words의 단어들을 비교하기 편하게 char배열로 변환 후 ArrayList에 넣기
        ArrayList<char[]> list = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            list.add(words[i].toCharArray());
        }
        
        //target도 한번씩 확인을 해야하기 때문에 미리 char배열로 만들어놓기
        char[] base = target.toCharArray();
        
       	//너비우선탐색인 BFS로 탐색하기 위해서 Queue 선언
        Queue<word> q = new LinkedList<>();
        
        //큐에 begin을 char배열로 변환하여 word 객체로 만들어서 넣기
        q.add(new word(0, begin.toCharArray()));
        
        //q가 비워질 때까지 반복
        while (!q.isEmpty()) {
        	//큐의 제일 상단 값 가져오기
            word w = q.poll();
            char[] temp = w.list;
            int index = w.index;
            
            //temp와 target이 같은지 안같은지 비교. 같으면 해당 index 리턴
            if (check(base, temp) == 0) return index;

			//temp와 list에 있는 단어들 비교
            for (int i = 0; i < list.size(); i++) {
                char[] data = list.get(i);
                //글자가 하나만 다르면 list에서 지우면서 q에 넣기
                if (check(temp, data) == 1) q.add(new word(index+1, list.remove(i)));
            }
        }
        return 0;
    }
    
    //a 글자와 b 글자가 몇 글자 다른지 비교하는 함수
    public int check(char[] a, char[] b) {
        int count = a.length;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == b[i]) count--;
        }
        
        return count;
    }
}

class word {
    int index;
    char[] list;
    public word (int i, char[] list) {
        this.index = i;
        this.list = Arrays.copyOf(list, list.length);
    }
}

 

테스트 1 〉	통과 (0.50ms, 83.1MB)
테스트 2 〉	통과 (0.40ms, 81.9MB)
테스트 3 〉	통과 (0.53ms, 69.9MB)
테스트 4 〉	통과 (0.39ms, 74.8MB)
테스트 5 〉	통과 (0.02ms, 75MB)