[JAVA] 백준 1316 그룹 단어 체커

1) 문제

https://www.acmicpc.net/problem/1316

2) 문제 접근

와아 예전에 풀어봤지만,, 초면인듯한 새로운 마음이였다.

나도 직접 문자 하나씩 보면서
이전 문자와 같으면 그냥 넘어가고,
이전 문자와 같지 않으면 새로운 문자니까
이미 나온 문자들을 담는 set에 이미 존재하는지/아닌지를 판별하는 식으로 진행해서 그룹단어인지 아닌지를 체크했다.

3) 풀이 1

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            String str = br.readLine();

            boolean group_words = true;
            HashSet<Character> set = new HashSet<>();
            int idx = 0;
            char prev = str.charAt(0);
            set.add(str.charAt(idx));

            while (idx < str.length()) {
                if (prev == str.charAt(idx)) {
                    idx++;
                } else {
                    prev = str.charAt(idx);
                    if (set.contains(str.charAt(idx))) {
                        group_words = false;
                        break;
                    }
                    set.add(str.charAt(idx));
                }
            }

            if (group_words) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}

3-2) 풀이 2

살짝 시간 복잡도가 커보여서 다른 분의 풀이를 참고해서 수정해보았다.
https://st-lab.tistory.com/69#recentEntries

달라진 점 :
HashSet을 쓰지 않고 각 알파벳이 나왔는지 아닌지를 담는 boolean[] 배열을 만들어서 진행한다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            boolean group_words = true;

            boolean[] check = new boolean[26];
            int prev = 0;

            for (int j = 0; j < str.length(); j++) {
                int now = str.charAt(j);

                if (prev != now) {
                    if (check[now - 'a'] == false) { // 해당 문자가 처음 나오는 경우
                        check[now - 'a'] = true;
                        prev = now;
                    } else { // 이미 나온 적 있으면
                        group_words = false;
                        break;
                    }
                }
            }

            if (group_words) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}