[Baekjoon] 백준 1316번: 그룹 단어 체커 (JAVA)

문제 1316

1316번: 그룹 단어 체커

[ 문제 풀이 ]

주어진 문자열을 한 단어씩 순회하면서 연속해서 나오는 문자들을 확인합니다. 연속해서 나온 문자들 중에 한 문자라도 떨어져서 나타나면 그룹 단어가 아닙니다.

kin의 경우 k, i, n이 연속해서 나타나므로 그룹단어입니다. 이를 고려해보았을 때, 다음과 같이 생각할 수 있습니다.

1. 문자열을 순회하면서 연속으로 나오는 문자들을 DFS 탐색을 통해 확인해줍니다.
2. HashSet<>을 이용하여 해당 문자가 HashSet<>에 없는 문자이면 처음 나타난 문자이므로 넣어줍니다.
3. HashSet<>에 이미 존재하는 문자라면 해당 문자는 그룹들과 떨어진 문자입니다. 
=> HashSet<>에 존재하는 문자들은 이미 앞에서 DFS 탐색을 통해 그룹으로(연속으로) 이루어진 문자이기 때문입니다.
4. flag 변수를 두어 현재 문자열이 그룹 단어인지를 true, false로 표시해줍니다. 따라서, 3번에서 이미 존재하는 문자인 경우 flag를 false로 두어 그룹단어가 아님을 표시한 후, break로 현재 문자열 순회에서 빠져나옵니다.
5. flag가 true인 경우에만 카운트를 증가시켜주면 됩니다. 아래 코드에서는 따로 HashSet<>을 하나 더 만들어 그룹 단어를 저장하고, size()를 출력하도록 했습니다.

DFS 탐색은 아래와 같이 구현하였습니다.
1. 현재 인덱스를 매개변수로 하여, 현재 위치와 그 다음의 위치의 문자들을 비교하여 같은 경우 DFS를 또 돌려줍니다.
2. visit[]을 활용하여 현재 인덱스의 방문 여부를 표시해줍니다. 이는 위에서 문자열을 순회할 때 연속된 같은 문자들을 continue로 건너뛰도록 하기 위함입니다.
3. 현재 인덱스가 size-1과 같으면 문자열의 맨 끝이므로 visit[idx] = true; 로 해주고 return 합니다.
(idx가 size-1과 같다는 것은 이전 인덱스의 문자와 같은 문자임을 알 수 있습니다.)

[ 코드 ]

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

public class Main {
    private static int size;
    private static String str;
    private static HashSet<Character> set = new HashSet<>();
    private static HashSet<String> res = new HashSet<>();
    private static boolean[] visit;
    private static boolean flag = true;

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

        for (int i = 0; i < N; i++) {
            str = br.readLine();
            size = str.length();
            visit = new boolean[size];
            set.clear();
            flag = true;
            for (int j = 0; j < size; j++) {
                char c = str.charAt(j);
                if (visit[j]) continue;
                if (set.contains(c)) {
                    flag = false;
                    break;
                } else {
                    set.add(c);
                }
                dfs(j);
            }
            if (flag) res.add(str);
        }

        bw.write(String.valueOf(res.size()));
        bw.flush();
    }

    private static void dfs(int idx) {
        if (idx == size-1) {
            visit[idx] = true;
            return;
        }

        visit[idx] = true;
        if (str.charAt(idx) == str.charAt(idx+1)) dfs(idx+1);
    }
}