알고리즘 공부
프로그래머스 단어변환(복습)
컴퓨터과학
2023. 10. 20. 23:46
https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=java
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
자바로 풀어봤습니다. 쉽네요 백트래킹 문제
import java.util.*;
class Solution {
public static String gbegin;
public static String gtarget;
public static String[] gwords;
public static boolean[] gbCheck;
public static int gn=0;
public static int gmincnt=0;
public Solution(){
}
void dfs(String start,int t ){
for(int k=0;k<gwords.length;k++){
int cnt=0;
int anw=0;
if(gbCheck[k]==false){
for(int i=0;i<gn;i++){
if( start.charAt(i) == gtarget.charAt(i)){
anw++;
}
if( start.charAt(i) == gwords[k].charAt(i)){
cnt++;
}
}
if(anw==gn){
if(gmincnt==0){
gmincnt=t;
}else {
if(gmincnt>t){
gmincnt=t;
}
}
return ;
}
if(cnt==gn-1){
gbCheck[k]=true;
dfs(gwords[k],t+1) ;
gbCheck[k]=false;
}
}
}
}
public int solution(String begin, String target, String[] words) {
int answer = 0;
gbegin=begin;
gtarget=target;
gwords=words;
Solution s= new Solution();
boolean[] bCheck=new boolean[words.length];
gbCheck=bCheck;
gn=begin.length();
s.dfs(begin,0);
answer=gmincnt;
return answer;
}
}