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

백준링크 : 바로가기

#문자열 #배열

문자열 문제는 아스키 코드와 if문 로직을 활용해 풀 수 있었다. 로직을 짜는데 귀찮음이 있었지만 복잡하더라도 경우의 수를 하나씩 해결해가며 올리면 성공 확률에 근접하는 듯하다.

이번 문제는 푸는데 실패했던 크로아티아 알파벳 문제보다 고려할 경우의 수가 적었다. 그 문제는 단어 내 문자열 수가 다른 글자들이 몇 개 포함되어 있는지를 찾아야 돼서 문자열 수가 달랐던 점이 힘들었다. 그룹 단어 체커는 알파벳이 연속해서 나오기만 하면 된다. 대신 이미 나온 알파벳이 다른 알파벳의 뒤에 다시 나오면 안된다. 그룹 단어가 아니라는 뜻이다. 

로직은 for문 3중첩을 이용했다. 최대 글자 수와 단어 수가 100개인 점을 감안했다. if문은 현재 charAt(i)와 다음 순서 charAt(i+1)을 비교해 연속이 이어지고 끊기는 지점을 파악했다. 연속이 끊기면 char 배열에 해당 charAt(i)를 저장했다. 그룹 단어 판별은 for문 중첩을 활용했다. 연속이 끊기는 지점에서 저장된 배열 내 char 들과 charAt(i+1)을 비교해 같으면 div++ int 변수를 증가해 1보다 작을 때 그룹 단어 cnt를 증가시켜 주었다. 

아스키 코드와 boolean 배열을 사용해 짠 코드를 리뷰해봤는데 어우 복잡하다. 다만 for문 중첩을 한 단계 줄였기 때문에 O(n) 시간복잡도 제곱을 3에서 2로 대폭 낮출 수 있는 장점이 있다. 로직은 알파벳이 모두 소문자라는 것에 주안점을 뒀고 charAt(i) - 97을 해줘서 boolean[26] 인덱스에 0~25까지 a,b,c,d....를 치환시켜 나왔던 값은 인덱스 값을 true로 변경해줬다.

그룹 단어가 아닌 조건1에 해당된다. 다음 조건은 연속된 알파벳인지 아닌지를 확인한다. 이전 알파벳을 char 변수 old에 담아줘서 조건문 &&을 사용했다. 그래서 그룹 단어의 조건 : if(!boolean[i] && new != old)가 나온다. 여기서 경우의 수를 고려하는 것이 중요하다. else로 그룹 단어가 아닌 조건을 일원화 시켜버리면 틀린다. 왜냐하면 경우의 수 하나가 더 있기 때문이다. "연속된 알파벳인 경우". 때문에 else if로 조건을 명시해야 한다. 그룹 단어가 아닌 조건 : else if(boolean[i] && new != old) 이미 나왔던 알파벳이며 직전 알파벳과 다를 경우, 그룹 단어가 아닌 조건을 충족시킨다. 

① 내가 짠 코드

package baekJoon.week7;
/*
    그룹단어란 한 문자가 연속해서 나타나는 경우만을 말한다. 각 문자는 붙어있어야 한다. 갯수는 상관없다.
    단어 N개를 입력 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.
    - 입력: 첫째 줄에 단어의 개수 N이 들어온다. 100보다 작거나 같은 자연수. 둘째 줄부터 N개의 단어가 들어온다. 소문자이고 중복되지 않으며
    길이는 최대 100이다.
    - 출력: 첫째 줄에 그룹 단어의 개수를 출력한다.
 */

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

public class GroupChecker_1316 {

    static int N;
    static String val;
    static char[] valAlphas;
    static int k = 0;
    static int div;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {

            val = br.readLine();
            valAlphas = new char[val.length()];

            for (int j = 0; j < val.length() - 1; j++) {

                if (val.charAt(j) == val.charAt(j + 1)) {

                } else {

                    for (char alpha :
                            valAlphas) {

                        if (alpha == val.charAt(j + 1)) {

                            div++;
                        }
                    }

                    valAlphas[k] = val.charAt(j);
                    k++;
                }
            } //단어 글자 반복문 종료
            if (div < 1) cnt++;
            //초기화
            div = 0;
            k = 0;
        }

        System.out.println(cnt);


    }
}

 

② 다른 사람 코드

package baekJoon.week7;
/*
    그룹단어란 한 문자가 연속해서 나타나는 경우만을 말한다. 각 문자는 붙어있어야 한다. 갯수는 상관없다.
    단어 N개를 입력 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.
    - 입력: 첫째 줄에 단어의 개수 N이 들어온다. 100보다 작거나 같은 자연수. 둘째 줄부터 N개의 단어가 들어온다. 소문자이고 중복되지 않으며
    길이는 최대 100이다.
    - 출력: 첫째 줄에 그룹 단어의 개수를 출력한다.
 */

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

public class GroupChecker_1316_ex {

    static int N;
    static String val;
    static boolean[] ck;
    static boolean group;
    static char old;
    static char nw;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {

            val = br.readLine();
            //true가 이미 나온 알파벳
            ck = new boolean[26];
            //그룹인지 아닌지 지시어
            group = false;
            //바로 직전 값
            old = val.charAt(0);
            //이미 나온 알파벳을 true로 변환
            ck[old - 97] = true;
            //그룹이 아닌 조건 : ck[i] = true; 면서 old와 다른 친구

            for (int j = 1; j < val.length(); j++) {

                nw = val.charAt(j);
                //그룹일 때
                if (!ck[nw - 97] && nw != old) {

                    ck[nw - 97] = true;
                    old = nw;
                }
                //그룹이 아닐 때
                else if (ck[nw - 97] && nw != old) {

                    group = true;
                    break;
                }
            } //단어 글자 반복문 종료

            if(!group) cnt++;
        } // 전체 반복문 종료

        System.out.println(cnt);


    }
}