생각정리/코딩테스트

[JAVA 알고리즘]BAEKJOON 1897번 토달기

생각중임 2024. 1. 18. 13:15

토달기

문제 설명

희현이는 원장선생님 말씀에 토를 다는 것을 몹시 좋아한다. 토를 단다는 것은 원장선생님께서 어떤 단어를 말씀하시면 그 단어의 맨 앞이나 중간, 혹은 맨 뒤에 한 글자를 끼워 넣어서 새로운 단어를 만드는 것으로, 버릇없는 행동과는 아무런 관계가 없는 순수한 단어 놀이이다.

희현이는 사전에 등재된 단어만을 사용한다. 사전은 d개의 단어로 구성되어 있으며, 각 단어는 80자 이내의 알파벳 소문자로만 이루어져 있다. 희현이는 원장선생님께서 어떤 단어를 말씀하셨을 때, 한 글자씩 토를 달아 사전에 등재된 단어를 계속 만들어 갈 경우, 가장 긴 단어를 만들려면 어떻게 해야 하는지가 궁금해졌다. 이를 해결하는 프로그램을 작성하라.

입력

첫 줄에 사전에 등재된 단어의 수 d와, 원장님이 처음 말씀하신 단어가 주어진다. (1 ≤ d ≤ 1,000) 원장님이 처음 말씀하신 단어의 길이는 세 글자이며, 사전에 있는 단어를 말씀하셨다. 다음 d개의 줄에는 사전에 등재된 단어가 한 줄에 하나씩 주어진다.

출력

첫 줄에 토달기 규칙을 지키며 단어를 만들어 갈 때, 만들 수 있는 단어 중 가장 긴 것을 출력한다. 답이 여럿일 경우 어느 것이나 상관없다.

제한사항

  • 없음

입출력 예

input return
9 cal
cal
calf
calfs
call
calls
choral
chorale
coal
coral		 chorale

문제 분석

새로운 단어를 만드는 규칙은 2가지이다.

  1. 맨 앞이나 맨 뒤에 한 글자를 넣어 전의 단어가 그대로 쓰이는 경우
  2. 단어 중간에 한 글자가 끼워지는 경우

단어의 길이가 순차적으로 늘어나기 때문에 주어진 단어를 오름차순 정렬을 시켜하는 것이 편해 보인다.

1번의 경우는 문자를 포함하는지 확인하면 알 수 있다.
2번의 경우가 복잡해지는데, 해당 단어를 하나씩 그전 단어와 체크를 해서 다른 곳이 한 곳인 인지를 보고 확인을 할 수 있다.

한 글자씩 확인할 때 순서의 중요한 점
똑같은 알파뱃의 종류이지만 순서로 인해 규칙에 안 맞을 수 있다.
c a l l -> c a e l l (가능)
c a l l -> c l a e l (불가능)

 

손으로 풀기

  1. 입력값을 담을 배열과 중복을 방지할 사용 여부를 확인할 배열을 만든다.
  2. 순서대로 확인을 하기 위해 입력값을 담은 배열을 오름차순으로 정렬한다.
  3. BFS 방식으로 문자 출력
    1. 큐가 빌 때까지 반복하면서 가장 긴 단어까지 반복한다.
    2. 현재 단어보다 한자리 긴 단어 중에 사용하지 않는 단어일 때, 
    3. 단어를 포함하면 큐에 넣어준다.
    4. 한 글자씩 비교해 틀린 부분이 한 곳이면 큐에 넣어준다.
    5. 큐에서 마지막에 나온 단어를 출력한다.
  4. DFS 방식으로 문자 출력
    1. 현재 단어보다 한자리 긴 단어중에 사용하지 않는 단어일 때, 
    2. 단어를 포함하면 단어를 재귀함수로 반복한다.
    3. 한 글자씩 비교해 틀린 부분이 한 곳이면 단어를 재귀함수로 반복한다.
    4. 반복을 하면서 단어의 길이를 비교해 가장 긴 단어를 출력한다.

나의 문제풀이

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

public class Main {
    
    static String[] words;
    static boolean[] visited;
    static String word = "";

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int d = Integer.parseInt(stringTokenizer.nextToken());
        String keyword = stringTokenizer.nextToken();

        words = new String[d];
        visited = new boolean[d];
        for (int i = 0; i < d; i++) {
            words[i] = bufferedReader.readLine();
        }
        Arrays.sort(words, (o1, o2) -> o1.length() - o2.length());

        visited[0] = true;
//        BFS(keyword);
        DFS(keyword);

        System.out.println(word);
    }

    public static void BFS(String keyword) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(keyword);

        while (!queue.isEmpty()) {
            word = queue.poll();

            for (int i = 1; i < words.length; i++) {
                // 다음 크기의 단어인지 확인을 한다.
                if (!visited[i] && word.length() + 1 == words[i].length()) {
                    // 한 글자가 앞, 뒤에 붙었을 경우 전 단어가 그대로 포함 된다.
                    if (words[i].contains(word)) {
                        queue.offer(words[i]);
                        visited[i] = true;
                        continue;
                    }

                    // 한 글자가 중간에 들어 갔을 경우 한 글자씩 순서에 맞게 확인을 해본다.
                    char[] beforeWord = word.toCharArray();
                    char[] afterWord = words[i].toCharArray();
                    boolean check = false;
                    for (int j = 0, k = 0; j < afterWord.length; j++) {
                        if (beforeWord[k] == afterWord[j]) {
                            k++;
                            continue;
                        }
                        if (!check) {
                            check = true;
                            continue;
                        }
                        if (check) {
                            check = false;
                            break;
                        }
                    }
                    // true로 나오면 1번만 다른 단어 false로 나오면 2번 이상 다른 단어
                    if (check) {
                        queue.offer(words[i]);
                        visited[i] = true;
                    }
                }
            }
        }
    }

    public static void DFS(String keyword) {

        if (word.length() < keyword.length()) {
            word = keyword;
        }

        for (int i = 1; i < words.length; i++) {
            // 다음 크기의 단어인지 확인을 한다.
            if (!visited[i] && keyword.length() + 1 == words[i].length()) {
                // 한 글자가 앞, 뒤에 붙었을 경우 전 단어가 그대로 포함 된다.
                if (words[i].contains(keyword)) {
                    visited[i] = true;
                    DFS(words[i]);
                    continue;
                }

                // 한 글자가 중간에 들어 갔을 경우 한 글자씩 순서에 맞게 확인을 해본다.
                char[] beforeWord = keyword.toCharArray();
                char[] afterWord = words[i].toCharArray();
                boolean check = false;
                for (int j = 0, k = 0; j < afterWord.length; j++) {
                    if (beforeWord[k] == afterWord[j]) {
                        k++;
                        continue;
                    }
                    if (!check) {
                        check = true;
                        continue;
                    }
                    if (check) {
                        check = false;
                        break;
                    }
                }
                // true로 나오면 1번만 다른 단어 false로 나오면 2번 이상 다른 단어
                if (check) {
                    visited[i] = true;
                    DFS(words[i]);
                }
            }
        }
    }
}

처음에 조건을 이전 문자와 다음 문자를 비교할 때, 그냥 한 글자를 가지고 있는 지를 확인을 하면서 그 글자를 제외하면서 가능여부를 확인을 하는 로직으로 만들어서 틀리게 나와 무슨 문제인지를 인지를 못하고 있다가 아예 풀이를 중단하고 쉬다가 다시 처음부터 문제를 분석하고 풀이를 하니 문자를 비교할 때 순서가 중요한 게 이제야 보였다.
문제를 풀면서 한 방법으로 너무 생각을 집중하면 간단히 보일게 안 보이게 될 수 있어 이점을 조심하고 풀리지 않는다면 처음부터 다시 생각을 해 환기 좀 시키기도 해야겠다.

알고리즘 분류

  • 자료 구조
  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색
  • 문자열
  • 해시를 사용한 집합과 맵

문제 출처 - https://www.acmicpc.net/problem/1897

 

1897번: 토달기

첫 줄에 사전에 등재된 단어의 수 d와, 원장님이 처음 말씀하신 단어가 주어진다. (1 ≤ d ≤ 1,000) 원장님이 처음 말씀하신 단어의 길이는 세 글자이며, 사전에 있는 단어를 말씀하셨다. 다음 d개

www.acmicpc.net