티스토리 뷰
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
이문제의 포인트는 주어진 단어의 한글자만 바꾼 단어가 주어진 단어의 집합에 있는지 확인하면서 진행해 나가는 과정이었다! 처음에는 단어를 바꾸니까 subString()을 쓰면 되겠다! 했는데 더 복잡해졌다는,,,,
문제풀이
-주어진 단어집합에 내가 비교하는 단어에서 한글자만 다른단어가 있는지 탐색
-visited == false라면 dfs에 그 단어로 다시 dfs진행
-target과 같아질때까지 비교
나는 한글자만 다른단어가 있는지 탐색하는 부분을 따로 checkWord라는 함수로 빼서 사용하였다.
public class Solution {
static int minCnt = Integer.MAX_VALUE;
public static void main(String[] args) {
String begin = "hit";
String target ="cog";
String[] words ={"hot", "dot", "dog", "lot", "log"};
dfs(new boolean[words.length],0,begin,target,words);
//해당 단어가 없을경우 0을 출력
if(minCnt==Integer.MAX_VALUE)
minCnt=0;
System.out.println(minCnt);
}
public static void dfs(boolean[] visited,int cnt,String begin,String target,String[] words){
//target과 일치하면 minCnt갱신해주기
if(begin.equals(target)){
if(minCnt>cnt)
minCnt=cnt;
return;
}
//단어집합에 존재하는 단어일 경우 dfs
for(int i=0;i<words.length;i++){
if(!visited[i] && checkWords(begin,words[i])){
visited[i]=true;
dfs(visited,cnt+1,words[i],target,words);
visited[i]=false;
}
}
}
//한글자만 바꾸는지 체크
public static boolean checkWords(String begin,String target){
char[] c1 = begin.toCharArray();
char[] c2 = target.toCharArray();
int change=0;
for(int i=0;i<c1.length;i++){
if(c1[i]!=c2[i]) change++;
}
if(change==1) return true;
return false;
}
}
'CS공부 > 알고리즘&문제풀이' 카테고리의 다른 글
[프로그래머스]완전탐색:숫자 야구(java) (0) | 2020.06.17 |
---|---|
[프로그래머스]DFS:여행경로(java) (0) | 2020.06.10 |
[프로그래머스]DFS:네트워크(java) (0) | 2020.06.04 |
[프로그래머스]DFS:타겟 넘버(java) (0) | 2020.06.03 |
[백준 14889]스타트와 링크/삼성 sw역량 테스트 기출(java) (0) | 2020.05.28 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- OS
- 최소 스패닝 트리
- dfs
- 분리 집합
- BFS
- Baekjoon
- Stomp
- 완전탐색
- sockjs
- git
- Oracle
- 삼성 sw역량 테스트
- 삼성 sw역량테스트
- JavaScript
- 프로그래머스
- SWEA
- MST
- 알고리즘
- 백준
- 정렬
- 운영체제
- DP
- programers
- 자바
- websocket
- Spring
- Heap
- 채팅
- java
- 코딩테스트
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함