[Java] BOJ 1897 토달기

1897번: 토달기

---

테스트 케이스

5 bcd
bcd
bcdd
abcdd
abcde
abcdde

---

오답 코드

• subString을 활용해서 한 글자씩 없애서 확인
• 위 테스트 케이스를 통과하지 못함

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int D;
    static String word, ans;
    static HashSet<String> set;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine(), " ");
        D = Integer.parseInt(st.nextToken());
        word = st.nextToken();

        set = new HashSet<>();
        for (int i = 0; i < D; i++) {
            set.add(br.readLine());
        }

        ans = word;
        for (String s : set) {
            if (check(s)) {
                if (ans.length() < s.length()) {
                    ans = s;
                }
            }
        }

        System.out.println(ans);
    }

    private static boolean check(String s) {
        if (s.equals(word)) {
            return true;
        }

        for (int i = 0; i < s.length(); i++) {
            String subString = s.substring(0, i) + s.substring(i + 1, s.length());
            if (set.contains(subString)) {
                return check(subString);
            }
        }

        return false;
    }
}

---

정답 코드

• 해싱을 사용해서 그래프로 구성
• 코딩 테스트에 자주 나오는 유형이니 알아두면 좋다

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int D;
    static String word, ans;
    static HashMap<String, Integer> map;
    static List<List<Integer>> list;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine(), " ");
        D = Integer.parseInt(st.nextToken());
        word = st.nextToken();

        map = new HashMap<>();
        for (int i = 0; i < D; i++) {
            map.put(br.readLine(), i);
        }

        list = new ArrayList<>();
        for (int i = 0; i < D; i++) {
            list.add(new ArrayList<>());
        }

        for (String s : map.keySet()) {
            List<Integer> checkList = check(s);
            for (int i : checkList) {
                int index = map.get(s);
                list.get(index).add(i);
            }
        }

        ans = word;
        int target = map.get(word);
        for (String s : map.keySet()) {
            int index = map.get(s);
            if (BFS(index, target) && ans.length() < s.length()) {
                ans = s;
            }
        }

        System.out.println(ans);
    }

    private static boolean BFS(int index, int target) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);

        boolean[] visit = new boolean[D];
        visit[index] = true;

        while (!queue.isEmpty()) {
            int pos = queue.poll();

            for (int next : list.get(pos)) {
                if (next == target) {
                    return true;
                }

                if (!visit[next]) {
                    visit[next] = true;
                    queue.add(next);
                }
            }
        }

        return false;
    }

    private static List<Integer> check(String s) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            String subString = s.substring(0, i) + s.substring(i + 1, s.length());
            if (map.containsKey(subString)) {
                list.add(map.get(subString));
            }
        }
        return list;
    }
}