[프로그래머스] 단어 변환 (java)

📖 문제

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

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

---

🔑 풀이

✅ HashMap<String, ArrayList<Integer>> graph: 각 단어 별로 변환할 수 있는 단어들을 저장한 map

✅ String[] newWords: words 배열에 begin을 추가한 배열

✅ String word1, word2: 단어의 한 알파벳을 뺀 결과 

1. words를 순회하며 target이 있는지 확인하고, newWords에 한 단어씩 저장한다
2. target이 없다면 0 반환
3. target이 있다면 newWords 마지막 원소로 begin을 추가한다
4. newWords를 순회하며 word1과 word2를 구해 같다면 graph에 추가한다
5. bfs를 실행하여 결과를 반환한다(target부터 한 알파벳씩 변환하여 begin 만듦)

✅ int bfs(String begin, String target)

1. queue에 target 넣기
2. visited에 <target,0> 넣기 (visited: <단어, 변환된 수>)
3. queue에서 단어를 꺼내 graph에서 변환할 수 있는 단어 찾기
4. 변환할 수 있는 단어가 visited에 없다면 큐에 넣고, visited 생성
5. 3~4를 반복하는데, 꺼내온 단어가 begin이라면 visited에서 변환된 수 반환

import java.util.*;

class Solution {

	public static HashMap<String, ArrayList<String>> graph;

	public static int solution(String begin, String target, String[] words) {
		int answer = 0;

		// target이 words에 있는지 확인하고, words에 begin을 추가
		boolean checkTarget = false;
		String[] newWords = new String[words.length + 1];
		for (int i = 0; i < words.length; i++) {
			// words에 있다면 true
			if (words[i].equals(target))
				checkTarget = true;
			newWords[i] = words[i];
		}
		// words에 없다면 0 반환
		if (!checkTarget)
			return 0;
		newWords[words.length] = begin;

		
		// 각 단어 별로 변환할 수 있는 단어를 map에 저장
		graph = new HashMap<>();
		for (int i = 0; i < newWords.length; i++) {
			ArrayList<String> al = new ArrayList<>();
			
			// word1: i번째 단어의 한 알파벳을 제거한 문자열 
			for (int j = 0; j < newWords[i].length(); j++) {
				String word1 = newWords[i].substring(0, j) + "" 
			+ newWords[i].substring(j + 1, newWords[i].length());
				
				// word2: k번째 단어의 한 알파벳을 제거한 문자열 
				for (int k = 0; k < newWords.length; k++) {
					if (k != i) {
						String word2 = newWords[k].substring(0, j) + ""
								+ newWords[k].substring(j + 1, newWords[k].length());
						// word1과 word2가 같다면 graph에 추가 
						if (word1.equals(word2))
							al.add(newWords[k]);
					}
				}
			}
			graph.put(newWords[i], al);
		}

		// bfs 실행 
		answer = bfs(begin, target);
		return answer;
	}

	public static int bfs(String begin, String target) {

		// target부터 변환 시작하여 begin 찾기 
		HashMap<String, Integer> visited = new HashMap<>();
		Queue<String> queue = new LinkedList<>();
		queue.offer(target);
		visited.put(target, 0);

		while (!queue.isEmpty()) {
			String pop = queue.poll();
			
			// 꺼내온 단어가 begin이라면 변환된 수 반환 
			if (pop.equals(begin))
				return visited.get(pop);
			
			for (String w : graph.get(pop)) {
				if (!visited.containsKey(w)) {
					queue.offer(w);
					visited.put(w, visited.get(pop) + 1);
				}
			}
		}
		return 0;

	}
}

---

오우쉣 

암만 생각해도 한알파벳씩 바꾸는 방법밖에 생각 안났음...

풀기는 빨리 풀엇는데 최악의 코드인듯 ㅎ

하지만 코딩테스트? 시간 안에 통과하면 그만인 거 아닌가요?

나 이은진 사고력은 조금 부족하지만 대단한 근성을 가졌지

수단과 방법을 가리지 않고 해낸다 ㅋ 

 

근데 3단계 문제는 풀고 난 다음에 남의 풀이 보면 이해가 잘 안됨

그게 뭔데? 왜이렇게 짧은데? 대체 뭔소린데?