프로그래머스 LV4 단어퍼즐 문제를 풀어봤다

https://school.programmers.co.kr/learn/courses/30/lessons/12983?language=java

1트

banana를 예를 들어서, an 단어의 경우 인덱스 1, 3 에서 나올 수 있다

이를 HashMap에 저장하고, BFS를 통해 탐색해서 최솟값을 찾는 방법으로 구현해봤다

import java.util.*;

class Solution {
    
    HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
    
    public int solution(String[] strs, String t) {
        
        int answer = 0;

				//HashMap 생성
        for(String str:strs){
            
            for(int i=0;i<t.length()-str.length()+1;i++){
                String temp = t.substring(i,i+str.length());
                if(temp.equals(str)){
                    ArrayList<Integer> list = map.getOrDefault(i,new ArrayList<>());
                    list.add(str.length());
                    map.put(i,list);
                }
            }
        }
        
        Queue<int[]> queue = new LinkedList<>();
        //0 : idx    1 : dis
        queue.add(new int[]{0,0});
        boolean[][] visited = new boolean[t.length()+1][t.length()+1];

				//BFS 탐색
        while(!queue.isEmpty()){
            
            int[] now = queue.poll();
            int nowIdx = now[0];
            int nowDis = now[1];
            if(nowIdx==t.length()) return nowDis;
            ArrayList<Integer> list = map.get(nowIdx); 
            if(list==null) continue;
            for(int idx=0;idx<list.size();idx++){
                //방문처리
                if(!visited[nowDis+1][nowIdx+list.get(idx)]){
                    visited[nowDis+1][nowIdx+list.get(idx)] = true;
                    queue.add(new int[]{nowIdx+list.get(idx),nowDis+1});
                }
                
            }
        }
        
        return -1;
    }
}

boolean 2차원 배열을 통해 dis에 대해서 방문처리 해준다

결과는….

또다시 시간초과 발생….

2트