[프로그래머스, 12983] 단어 퍼즐 (java)

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

프로그래머스

728x90

---

메모리: 54.3 MB, 시간: 45.78 ms

사용 알고리즘: BFS

 

만들고자 하는 문자열을 char 배열로 바꾸고,

0번 인덱스부터 사용할 수 있는 단어 조각을 찾는다.

 

사용할 수 있는 단어 조각이 있다면,

해당 단어 조각을 사용했을 때의 길이(다음으로 확인해주어야 하는 인덱스)와

사용한 단어 조각 개수를 배열에 담아

이어서 붙일 단어 조각을 찾을 대기열인 큐에 넣어준다.

 

단, n개의 단어 조각 조합으로 i 길이의 문자열을 만드는 경우를 찾았을 때

i 길이의 문자열을 만들 수 있는 경우 중, 단어 조각을 n개 사용하는 것이 최소인 경우에만큐에 넣어준다.

import java.util.*;

class Solution {
    public int solution(String[] strs, String t) {
        
        // 단어 조각을 char 배열로 변환
        char[][] strsArr = new char[strs.length][];
        for(int i = 0; i < strs.length; i++) {
            strsArr[i] = strs[i].toCharArray();
        }
        
        // 완성해야 하는 문자열 char 배열로 변환
        char[] tArr = t.toCharArray();
        
        // 더 적은 단어 조합을 발견했을 경우에만 진행
        int[] count = new int[tArr.length];
        Arrays.fill(count, Integer.MAX_VALUE);
        
        // 문자열 조합 정보
        // 배열[0] := 시작 인덱스
        // 배열[1] := 몇 개의 단어를 사용했는지
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {0, 0});
        
        int answer = -1;
        
        int[] now; boolean flag;
        while(!q.isEmpty()) {
            now = q.poll();
            
            // now[0]부터 동일한 단어 조각이 있는지 확인
            for(int i = 0; i < strsArr.length; i++) {
                flag = true;
                for(int j = 0; j < strsArr[i].length; j++) {
                    if(now[0] + j >= tArr.length || tArr[now[0] + j] != strsArr[i][j]) {
                        flag = false;
                        break;
                    }
                }
                // 연결할 수 있는 단어 조각이라면
                if(flag) {
                    // 단어를 완성한 경우
                    if(now[0] + strsArr[i].length == tArr.length) {
                        answer = answer == -1 ? now[1] + 1 : Math.min(answer, now[1] + 1);
                    }
                    // 더 적은 단어 조각으로 문장을 완성할 수 있는 경우
                    else if(count[now[0] + strsArr[i].length] > now[1] + 1){
                        count[now[0] + strsArr[i].length] = now[1] + 1;
                        q.add(new int[] {now[0] + strsArr[i].length, now[1] + 1});
                    }
                }
            }
        }

        return answer;
    }
}