뒤죽박죽 코딩 이야기

2022년 2월 12일 토요일 - 주말은 최고야!

오늘 올려볼 문제는 127번 Word Ladder 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

와 오늘 진짜 못푸는줄 알았다...

입력

사진에서도 볼 수 있듯이 String 2개와 String 리스트 하나가 주어진다.

풀이 및 코드

문제를 설명하기가 조금 어렵긴 한데 beginWord를 endWord로 wordList를 사용해서 변환할 수 있는지, 있다면 가장 짧은 변환 횟수는 몇인지 구하는 문제이다.

이 때 변환하는 규칙은 String을 구성하는 문자들 중 하나만 다른 String으로만 변환이 가능하다.

오늘은 정말 어려웠다.

일단 String으로 주어지기에 HashMap을 써야한다는 것을 알았다.

HashMap에 문자가 1개만 차이나는 String ArrayList를 저장하고 또한 Visit을 저장하는 HashMap도 만든다.

이를 모두 저장하고 재귀를 사용하여 순회하는 방식으로 문제를 풀었다.

하지만 DFS로 푸는 바람에 Time Limit Exceeded가 났다.

그래서 다른 풀이를 생각해봤다.

BFS가 최소 길이를 찾는다는 것을 생각해냈고 이를 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    // key와 문자 1개만 차이나는 String들을 담고있는 HashMap
    HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
    // visit 했는지 판단
    HashMap<String, Boolean> visit = new HashMap<String, Boolean>();

    // endWord 파라매터로 넘기기 싫어서 글로벌
    String end;

    // wordList의 길이가 최대 5000이므로 10000으로 설정
    int result = 10000;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // HashMap에 value로 들어있는 ArrayList를 받기 위한 변수
        ArrayList temp;

        end = endWord;

        // beginWord는 wordList에 없을 수 있기 때문에 beginWord에 대해서 초기화
        map.put(beginWord, new ArrayList<String>());
        visit.put(beginWord, false);

        // endWord가 wordList에 포함되어 있는지 판단하는 변수
        boolean hasEnd = false;

        // wordList에 들어있는 String에 대한 초기화 과정
        // 또한 begin에 대한 것도 처리해줌
        for(int i = 0; i < wordList.size(); i++)
        {
            map.put(wordList.get(i), new ArrayList<String>());
            visit.put(wordList.get(i), false);

            if(check(beginWord, wordList.get(i)))
            {
                // HashMap에서 get해서 바로 Add 하면 put이 안돼서 temp로 받아서 add 하는 과정
                temp = map.get(beginWord);
                temp.add(wordList.get(i));
                map.put(beginWord, temp);
            }

            if(wordList.get(i).equals(endWord))
                hasEnd = true;
        }

        // endWord가 wordList에 없다면
        if(!hasEnd)
            return 0;

        // String끼리 문자 차이가 1개만 나는 String 들을 HashMap에 저장하는 과정
        for(int i = 0; i < wordList.size(); i++)
        {
            // beginWord가 wordList에 들어있을 경우 2번 저장되게 되므로 그거 막아주는 역할
            if(wordList.get(i).equals(beginWord))
                continue;

            for(int j = i + 1; j < wordList.size(); j++)
            {
                if(check(wordList.get(i), wordList.get(j)))
                {
                    temp = map.get(wordList.get(i));
                    temp.add(wordList.get(j));
                    map.put(wordList.get(i), temp);

                    temp = map.get(wordList.get(j));
                    temp.add(wordList.get(i));
                    map.put(wordList.get(j), temp);
                }
            }
        }

        // BFS를 위한 큐
        Queue<String> q = new LinkedList<String>();
        q.add(beginWord);

        solve(q, 1);

        return result == 10000 ? 0 : result;
    }

    // 이 메소드는 평범한 BFS와 로직이 같다.
    public void solve(Queue<String> q, int level)
    {
        Queue<String> next = new LinkedList<String>();
        ArrayList<String> arr;

        while(!q.isEmpty())
        {
            arr = map.get(q.poll());

            for(int i = 0; i < arr.size(); i++)
            {
                if(!visit.get(arr.get(i)))
                {
                    visit.put(arr.get(i), true);
                    next.add(arr.get(i));
                }

                if(arr.get(i).equals(end))
                {
                    result = level + 1;
                    return;
                }
            }
        }

        if(!next.isEmpty())
            solve(next, level + 1);
    }

    // 문자 1개만 차이나는지 판단하는 메소드
    public boolean check(String s1, String s2)
    {
        if(s1.length() != s2.length())
            return false;

        int diff = 0;

        for(int i = 0; i < s1.length(); i++)
        {
            if(s1.charAt(i) != s2.charAt(i))
                diff++;
        }

        return diff == 1;
    }
}

제출 화면

오늘은 진짜 못푸는줄 알았다.

푸는데 1시간 30분 걸렸으니 말 다 했다...

그래도 풀어서 블로그에 글 쓸 수 있어서 다행이다!

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.