[Algorithm] 프로그래머스 Lv3 단어 변환

안녕하세요 rosepurple입니다. :)

오늘 푼 알고리즘 문제 풀이를 작성해보도록 하겠습니다!

문제

오늘은 아래 문제를 풀어봤습니다. (약 50분 소요)

programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

풀이

int answer;
boolean[] visited;

dfs로 풀이하기 위해서 전역 변수로 answer과 visited를 선언해주었습니다.

visited는 확인한 단어는 true, 확인하지 않은 단어는 false로 초기화하는 배열입니다.

 

answer = 51;
visited = new boolean[words.length];

위의 변수들은 solution 메서드 안의 변수들입니다.

문제에서 단어들이 들어있는 words 배열의 최대 크기가 50이라고 했으므로, answer는 51로 초기화합니다.

그리고 words 배열의 크기만큼 visited도 초기화해줍니다.

 

dfs(begin, target, words, 0);

private void dfs(String begin, String target, String[] words, int count) {
    if (begin.equals(target)) {
        answer = (answer > count)? count: answer;
        return;
    }

    for (int i = 0; i < words.length; i++) {
        if (!visited[i] && checkValidation(begin, words[i])) {
            visited[i] = true;
            dfs(words[i], target, words, count + 1);
            visited[i] = false;
        }
    }
}

그 후에 dfs 메서드를 실행시킵니다.

dfs 메서드는 위와 같은데, 변환한 현재 단어(begin)와 최종 변환해야 할 단어(target)가 같다면, 전역 변수인 answer과 비교하여 작은 값을 answer에 넣어줍니다.

현재 단어(begin)와 최종 변환해야할 단어(target)가 다르다면 words 배열을 순회합니다.

체크하지 않은 단어이고, 현재 단어와 한 글자만 다른 단어라면 visited 배열의 인덱스를 true로 바꾸고, dfs를 다시 실행해줍니다.

 

private  boolean checkValidation(String begin, String target) {
    int notEqualChar = 0;

    for (int i = 0; i < begin.length(); i++) {
        if (begin.charAt(i) != target.charAt(i)) notEqualChar++;
    }

    return (notEqualChar == 1)? true: false;
}

단어를 체크하는 checkValidation 메서드는 위와 같습니다.

현재 단어(begin)와 다른 글자를 카운트하는 notEqualChar를 0으로 초기화해줍니다.

그 후에 현재 단어(begin)와 비교하는 단어(target)를 한 character씩 비교해 만약 다른 character라면  notEqualChar를 1씩 추가해줍니다.

 

모두 비교했다면 notEqualChar가 1일 경우에만 true로 리턴해줍니다.

 

전체 코드

class Solution {
    int answer;
    boolean[] visited;

    public int solution(String begin, String target, String[] words) {
        answer = 51;
        visited = new boolean[words.length];

        dfs(begin, target, words, 0);

        return (answer > 50)? 0: answer;
    }

    private void dfs(String begin, String target, String[] words, int count) {
        if (begin.equals(target)) {
            answer = (answer > count)? count: answer;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (!visited[i] && checkValidation(begin, words[i])) {
                visited[i] = true;
                dfs(words[i], target, words, count + 1);
                visited[i] = false;
            }
        }
    }

    private  boolean checkValidation(String begin, String target) {
        int notEqualChar = 0;

        for (int i = 0; i < begin.length(); i++) {
            if (begin.charAt(i) != target.charAt(i)) notEqualChar++;
        }

        return (notEqualChar == 1)? true: false;
    }
}

 

마무리

만약 궁금한 점이 있으시다면 편하게 댓글 남겨주세요!

이번 포스팅도 읽어주셔서 감사합니다. :)