250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
Tags
- 코드업 배열
- 해커랭크
- Java
- 프로그래머스
- 프로세스개념
- 2차원 달팽이 배열
- 운영체제의역할
- 다할수있다
- 성실한 개미
- 운영체제 컴퓨터 향상
- 100제 문제
- 100제
- 자바
- 운영체제
- MLQ
- MFQ
- 설탕뽑기
- 2차원행열
- 코딩을지탱하는기술
- 책
- 가즈아
- 문해력 수업
- 네트워크
- CPU 스케줄링
- 양뱡향
- 기초 100제
- 운영체제의 분류
- 운영체제의 구동
- 운영체제 개요
- 코드업
Archives
- Today
- Total
개발로그
[프로그래머스] 단어변환 - JAVA 본문
728x90
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- 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 합니다.
입출력 예
begin target words return
"hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] 4
"hit" "cog" ["hot", "dot", "dog", "lot", "log"] 0
문제 풀이 :
begin값을 첫 시작으로 words안에있는 단어들중에 한글자만 다른 값에 대해서 리턴을 해주는 문제이다.
처음에는 이해를 못했고 강의를 보고 아 이런문제구나 라고 생각하고 풀이 보면서 이해했다.
class Data {
String word;
int dep;
Data(String word,int dep) {
this.word = word;
this.dep = dep;
}
}
public class worksTrans {
public static void main(String[] args) {
String begin = "hit";
String target = "cog";
String[] words = {
"hot", "dot", "dog", "lot", "log", "cog"
};
// 최대값
int answer = words.length;
if(!Arrays.asList(words).contains(target)) answer = 0;
// 사용한 단어인지 아닌지를 찾음.
Set<String> us = new HashSet<>();
// DFS
Stack<Data> st = new Stack<>();
st.add(new Data(begin,0));
while (!st.isEmpty()) {
Data now = st.pop();
if(now.word.equals(target)) {
answer = now.dep;
}
for(String w : words) {
// 한글자만 다른 단어
// 사용하지 않은 단어
if(chg(now.word,w)) continue;
if(us.contains(w)) continue;
// 사용하는 단어
System.out.println(w);
us.add(w);
st.add(new Data(w,now.dep + 1));
}
}
System.out.println(answer);
}
static boolean chg(String w1, String w2) {
// 숫자가 다를수가있기때문에.
int len = Math.min( w1.length(), w2.length() );
int cnt = 0;
for(int i = 0 ; i < len && cnt < 2; i++) {
if(w1.charAt(i) != w2.charAt(i)) cnt++;
}
return cnt == 1;
}
728x90
'코딩테스트' 카테고리의 다른 글
[프로그래머스] 가장 먼 노드- JAVA (0) | 2022.05.15 |
---|---|
[프로그래머스] 더 맵게- JAVA (0) | 2022.05.15 |
[프로그래머스] 게임 맵 최단거리- JAVA (0) | 2022.05.14 |
[프로그래머스] 타겟 넘버 - JAVA (0) | 2022.05.11 |
[프로그래머스] 네트워크 - JAVA (0) | 2022.05.10 |