[백준 문제 풀이] 1316번 그룹 단어 체커

Junu Kim·2025년 7월 2일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

2/46

[1316] 그룹 단어 체커

난이도: ★★☆☆☆ • solved on: 2025-07-02

문제 요약

문제 유형: 문자열 처리, 구현
요구사항: 주어진 N개의 단어 중 그룹 단어(group word)인 단어의 개수를 구해야 한다.

사용 개념

자료구조
- char[] : 입력 단어를 한 글자씩 분리해 저장 (불변성이 특징, immutable)
알고리즘/기법
- 순회
- 문자열 처리

풀이 아이디어 및 코드

방법 1 : 각 단어에 대한 순회 + 만난 알파벳 저장

문제 분해

각 단어를 문자 단위로 한 글자씩 순회한다.

이전 문자와 같으면 연속 등장으로 간주하고 넘어간다.

이전 문자와 다르고, 이미 tmpWordList에 등장 기록이 있으면 그룹 단어가 아니므로 개수에서 제외한다.

검사 통과 시 tmpWordList에 현재 문자를 추가하고 다음 글자 검사로 넘어간다.
핵심 로직 흐름
for each word:
    tmpWordList = ""                       // 그룹 단어 판별을 위한 기록 문자열
    resultWordList += word[0]             // 첫 글자 기록
    for j from 1 to word.length-1:
        if word[j] == word[j-1]:
            continue                       // 연속 등장인 경우 무시
        else if tmpWordList.contains(word[j]):
            resultCount--                 // 이미 등장했던 문자(비연속) → 제외
            break
        else:
            tmpWordList += word[j]        // 새로운 문자 기록
예외 처리

단어 길이가 1인 경우: 무조건 그룹 단어로 판단

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int textCount = sc.nextInt();
        int resultWord = textCount;

        for (int i = 0; i < textCount; i++) {
            char[] word = sc.next().toCharArray();
            String tmpWordList = "";

            for (int j = 0; j < word.length; j++) {
                if (j == 0) {
                    tmpWordList += word[j];
                } else {
                    if (word[j] == word[j - 1]) {
                        continue;
                    } else {
                        if (tmpWordList.contains(word[j] + "")) {
                            resultWord--;
                            break;
                        } else {
                            tmpWordList += word[j];
                        }
                    }
                }
            }
        }

        System.out.println(resultWord);
    }
}

방법 2 : 알파벳의 ASCII를 활용한 Boolean 매핑 및 중복 검사

문자 등장 기록

String tmpWordList 대신 boolean[] seen = new boolean[26] 사용

알파벳 26글자만 체크하므로 공간도 O(1)

이전 문자 추적

char prev = word[0] 로 직전 문자를 저장

새 문자 c 가 prev 와 다를 때만

seen[c - 'a'] 검사

이미 true → 그룹 단어 아님

아니면 true로 표시하고 prev = c 갱신

I/O 최적화

Scanner 대신 BufferedReader + StringTokenizer 사용

출력은 StringBuilder 에 모아 한 번에 출력

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder   sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int count = n;

        while (n-- > 0) {
            String s = br.readLine();
            boolean[] seen = new boolean[26];
            char prev = s.charAt(0);
            seen[prev - 'a'] = true;

            for (int i = 1; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == prev) continue;           // 연속 등장 무시
                if (seen[c - 'a']) {               // 비연속 중복 체크
                    count--;
                    break;
                }
                seen[c - 'a'] = true;              // 새 문자 기록
                prev = c;
            }
        }

        sb.append(count);
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1 :

시간 복잡도 : O(N × L²)

공간 복잡도 : O(1) (입력 처리용 버퍼 제외)

방법 2 :

시간 복잡도 : O(N × L)

공간 복잡도 : O(1) (입력 처리용 버퍼 제외)

어려웠던 점

연속 등장인 경우와 비연속 중복인 경우를 구분하는 조건문 설계에서 로직이 꼬여 디버깅에 오래 걸렸다.
tmpWordList.contains를 쓸 때 문자열 연결(+=)로만 관리하다 보니, 문자가 중복되었는지 확인 후 처리 흐름을 바로 끊는 부분을 놓쳐 여러 번 테스트를 반복했다.

방법 1로 시도할 때 효율을 생각하고 만들지 않았기에 테스트 시간이 좀 걸리고 용량도 다른 Java 코드에 비해 많았다.

배운 점 및 팁

HashSet을 사용하면 contains 검사 시 O(1)에 해결할 수 있어 시간 복잡도를 O(N×L)으로 줄일 수 있다.
다수의 문자열 입력이 있을 때는 Scanner보다 BufferedReader + StringBuilder 조합이 입출력 속도가 더 빠르다.
문자 범위가 고정된 경우, boolean[]이 HashSet보다 더 가볍고 빠르다.