알고리즘/프로그래머스
[프로그래머스] 단어 변환 Java 풀이 및 해설
승민아
2024. 4. 7. 13:29
https://school.programmers.co.kr/learn/courses/30/lessons/43163
풀이 방법
- Lv.3 단계라 다들 BFS는 잘 이해하고 있을 것이다. BFS로 풀었다.
- 핵심은 문자 하나를 바꿔서 탐색이 가능한 word라 하더라도 최소가 되는 비용으로 탐색이 가능할때 큐에 삽입하는 것이다.
- 왜냐 탐색 비용이 최소가 될 수 없는데 탐색하는 것은 최소 값을 구하는 문제에서 의미없는 탐색이기 때문이다.
전체 코드
import java.util.*;
class Solution {
class Pair {
String word;
int cnt;
public Pair(String word, int cnt) {
this.word = word;
this.cnt = cnt;
}
}
public int solution(String begin, String target, String[] words) {
int answer = 0;
int cost[] = new int[50];
for(int i=0; i<50; i++)
cost[i] = 9876;
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(begin, 0));
// Queue에는 empty()가 없고 size()를 써야함...
while(q.size() != 0) {
String word = q.peek().word;
int cnt = q.peek().cnt;
q.remove();
for(int i=0; i<words.length; i++) {
int diff = 0; // 차이나는 글자수
// 충격. 배열은 필드 length이지만 String에서는 메서드 length()임.
for(int j=0; j<words[i].length(); j++) {
// 또 다시 충격.. String str = "abc"일때 str[0]은 못함 str.charAt(0) 써야함.!
if(words[i].charAt(j) != word.charAt(j))
diff++;
}
// 글자 수 차이가 1이고, 비용이 더 싸게 진입 가능하다면
if(diff == 1 && cnt+1 < cost[i]) {
cost[i] = cnt+1;
q.add(new Pair(words[i], cnt+1));
}
}
}
// words에 target이 존재하면 answer 갱신
for(int i=0; i<words.length; i++) {
if(target.equals(words[i]))
answer = cost[i];
}
return answer;
}
// Queue, length, length(), C++ pair<> -> 클래스 만들어 사용하기, charAt
// Stack에서는 push(), pop() 이였지만 Queue에서는 add(), remove()
}