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

이 글은 읽는데 약 7분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

403 Forbidden
www.acmicpc.net

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

출력

첫째 줄에 그룹 단어의 개수를 출력한다.

요약

입력이 그룹 단어인지 확인하는 프로그램을 짠다.

그룹 단어는 주어진 단어에서 어떤 알파벳이 1번 이상 연속되어야 하며(즉 한번만 나와도 된다), 일단 나왔던 알파벳이 연속되지 않고 뒤에서 다시 나오는 것은 안된다.

abc -> 그룹단어
abbccc -> 그룹단어
abca -> 그룹단어 아님 (a가 연속되지 않은 상태에서 뒤에서 다시 나옴)
abcaa -> 그룹단어 아님 (위와 같은 이유)

나의 코드 (int 배열 사용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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[] alphabet = new int[26];  // 하나의 케이스에서 알파벳이 연속으로 몇 번 나왔나 횟수를 저장하는 배열
        int cnt = 0;  // 그룹문자의 개수
        
        for(int i=0; i<N; i++){
            char[] word = br.readLine().toCharArray();  // 단어를 입력받아 char 배열로 변환
            int prev = word[0];  // 이전 문자를 저장. 초기값은 첫번째 문자와 동일하게
            boolean isGroup = true;  // 현재 단어가 그룹 단어인지 여부 플래그
            
            for(int j=0; j<word.length; j++){  // 각 글자별로 반복
                int code = (int) word[j];  // 현재 글자의 아스키코드 값

                // 만약 이전 문자가 현재 문자와 다르면서, 이전에 한 번이라도 나온적이 있다면
                if(prev != code && alphabet[code - 97] != 0){
                    isGroup = false;  // 그룹문자 아니다
                    break;  // 더이상 확인할 필요 없으므로 break
                }else{
                    alphabet[code - 97]++;  // 아니면 해당 알파벳의 출현 횟수를 +1
                }
                prev = word[j];  // 다음 문자로 넘어가기 전 이전 문자를 현재 문자로 지정한다
            }
            
            if(isGroup) cnt++;  // 그룹 문자면 개수 +1
            alphabet = new int[26];  // 출현 횟수 저장용 배열을 초기화
        }
        
        System.out.println(cnt);
        br.close();
    }
}

입력된 단어를 한 글자씩 쪼갠다음 처음부터 순서대로 본다.

글자 하나를 확인할 때 이전 글자와 같은지 확인한다.
만약 이전 글자와 다른 경우 현재 글자의 출현 횟수도 확인하는데, 이 때 횟수가 0이 아니면 연속되지 않은 상태로 이전에 나온적이 있다는 뜻이므로 그룹 단어가 아니게 되니 바로 스킵한다.
이 때 그룹 단어 여부를 저장하는 플래그 변수를 거짓으로 변경한다.

아니면 즉, 이전 글자와 현재 글자가 같거나, 같지 안더라도 출현 횟수가 0이면 다음 글자를 계속 확인한다.

이후 모든 글자를 다 확인한 후 또는 중간에 break가 걸려서 확인이 끝났을 때 플래그 변수를 확인한다.
기본값이 참이므로, break 걸리면서 false로 바뀌지 않았다면 그룹 단어이게 되므로 카운트를 +1한다.

나의 코드 (boolean 배열 사용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
        boolean[] isExists = new boolean[26];
        int cnt = 0;
        
        for(int i=0; i<N; i++){
            char[] word = br.readLine().toCharArray();
            int prev = word[0];
            boolean isGroup = true;
            
            for(int j=0; j<word.length; j++){
                int code = (int) word[j];
                if(prev != code && isExists[code - 97]){
                    isGroup = false;
                    break;
                }else{
                    isExists[code - 97] = true;
                }
                prev = word[j];
            }
            
            if(isGroup) cnt++;
            isExists = new boolean[26];
        }
        
        System.out.println(cnt);
        br.close();
    }
}

사실 글자의 이전 출현 여부만 확인하면 되므로 굳이 int 배열로 출현 횟수를 셀 필요 없이 boolean 배열로 출현 여부만 저장해도 된다.

추가로 제출해보니 int 배열 코드는 128ms/14228KB가 나왔고, boolean 배열 코드는 124ms/14160KB로 boolean 쪽이 근소하게 더 빨랐다.

댓글