[프로그래머스][Java][Lv. 3] 단어 변환

문제 설명

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

 

---

 

제한 사항

 

---

 

입출력 예

 

---

 

풀이

import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;

class Solution {
    ArrayList<String> wordList = new ArrayList<>();
    HashSet<String> check = new HashSet<>();
    
    public int solution(String begin, String target, String[] words) {
        return bfs(List.of(begin), words, target, 0);
    }
    
    private int bfs(List<String> prevList, String[] words, String target, int answer) {
        ArrayList<String> nextList = new ArrayList<>();
        
        for (String prev : prevList)  {
            for (int i = 0; i < prev.length(); i++) {  // 한 글짜씩 순회
                for (String word : words) {
                    if (check.contains(word)) continue;
                    
                    String regex = new StringBuilder(prev).replace(i, i + 1, ".").toString();
                    if (word.matches(regex) && !word.equals(prev)) {
                        if (word.equals(target)) return ++answer;
                        nextList.add(word);
                        check.add(word);
                    }
                }
            }
        }
        if (nextList.isEmpty()) return 0;
        else return bfs(nextList, words, target, answer + 1);
    }
}

 

---

 

후기

현재 단어를 한 글자씩 순회하면서 words에 정규표현식 조건에 맞는 문자열이 있으면 다음 리스트에 추가하는 식으로 접근했다. 반복문 중첩이 많이 되기 때문에 제한사항에서 단어 길이가 길거나 words 길이가 길면 다른 방식으로 접근해야 할 수도 있다.