백준 1316 "그룹 단어 체커" (JAVA)

🔍 문제링크

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

---

📌 문제 요약

• 그룹 단어: 같은 문자가 연속해서 나오는 단어.

aba ❌ (a가 떨어져서 등장) → 그룹 단어 아님
abba ❌ (a가 떨어져서 등장) → 그룹 단어 아님
abc ✅ → 그룹 단어

• 입력된 N개의 단어 중 그룹 단어의 개수를 출력.

---

🛠 풀이 및 알고리즘

1. 단어를 앞에서부터 탐색하면서 연속되지 않은 문자가 나온 경우 체크
   • 현재 문자가 이전 문자와 다르다면, 이미 나온 문자인지 확인.
   • 이전에 등장한 적 있다면 그룹 단어가 아님 (false 반환).
2. 중복 문자 체크를 위해 HashSet 사용
   • 문자가 등장했는지 빠르게 확인 (O(1)).
3. 모든 단어를 검사하고 그룹 단어의 개수를 출력

---

💡 코드

public class Baekjoon_1316 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            if (isGroupWord(s)) {
                ans++;
            }
        }
        System.out.println(ans);
    }

    private static boolean isGroupWord(String s) {
        Set<Character> set = new HashSet<>();
        char prev = s.charAt(0);
        set.add(prev);
        for (int i = 1; i < s.length(); i++) {
            char now = s.charAt(i);
            if (now != prev && set.contains(now)) { // 이전에 나온 문자가 떨어져서 다시 등장
                return false;
            }
            set.add(now);
            prev = now;
        }
        return true;
    }
}

---

🏆 시간 복잡도 분석

• 각 단어 길이 L에 대해 O(L) 수행 (HashSet은 O(1))
• N개의 단어를 검사하므로 총 O(NL).
• 최악의 경우 N = 100, L = 100 → O(10,000)