백준) 1316 : 그룹 단어 체커

⏰문제

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

1316번: 그룹 단어 체커

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

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

 

입력

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

 

출력

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

 

예제 입력 1

3
happy
new
year

예제 출력 1

3

예제 입력 2

4
aba
abab
abcabc
a

예제 출력 2

1

예제 입력 3

5
ab
aa
aca
ba
bb

예제 출력 3

4

예제 입력 4

2
yzyzy
zyzyz

예제 출력 4

0

예제 입력 5

1
z

예제 출력 5

1

예제 입력 6

9
aaa
aaazbz
babb
aazz
azbz
aabbaa
abacc
aba
zzaz

예제 출력 6

2

 

💡풀이

문제에서 문자열이 주어질 때 ccazzzzbb와 같이 문자가 연속되어서 들어오면 정답의 개수를 하나 올려준다. 

하지만 aabbbccb라는 문자열처럼 b가 다른 b들과 연속되지 않고 혼자 떨어져있다. 이것은 정답으로 여기지 않는다. 

 

내가 풀은 방식은 아래와 같다. 1. 들어온 문자열 하나당 해당 알파벳의 index를 저장하는 알파벳배열과 해당 알파벳을 방문했는지를 확인하는 boolean배열을 만든다.

int[] alpha = new int[26];
boolean[] check = new boolean[26];

- alpha

배열의 index는 알파벳 / 해당 index의 값은 문자열의 index이다.   예를 들어 happy라는 값을 for문이 돌아 현재 'h'라면 alpha[h] = 0이 들어가는 것과 같다. - check 배열의 index : 알파벳 / 해당 알파벳을 들린적이 있는지 

 

2. 문자열의 길이만큼 for문을 돌면서 해당 알파벳이 처음 등장했는지 아닌지를 check 배열을 통해 판단한다.     2-1. 처음 방문O    - 처음 방문했다면 알파벳 배열에 해당 문자가 문자열에서 몇 번째인지 저장.     - 해당 방문 배열 true     2-2. 처음 방문X. 이미 방문     - 방문했다면 이미 알파벳 배열에 값이 들어가있을 것이다. 이 때 새로 들어온 문자의 index와 이미 들어있는 문자의      index가 차이가 1보다 크다면 연속된 것이 아니라는 것. 그렇기 때문에 flag라는 변수를 false로 만들어준다. 

    - 하지만 차이가 1이라면 연속해서 들어오는 문자인 것이다. 

 

⌨️ 코드

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 answer =0;
        for(int i=0; i< N; i++){
            int[] alpha = new int[26];
            boolean[] check = new boolean[26];

            String str = br.readLine();
      
            boolean flag = true;
            for(int j = 0; j < str.length(); j++){
                char c = str.charAt(j); //a
                int idx = c-'a';

                if(!check[idx]){//방문하지 않았다면
                    alpha[idx] = j;
                    check[idx] = true;
                }
                else{//방문했다면
                    if(j - alpha[idx] > 1){ //1보다 크다는 것은 바로 옆에 있지 않다는 것
                        flag = false;
                        break;
                    }
                    else if(j - alpha[idx] == 1){ //1이라면
                        alpha[idx] = j;
                    }
                }
            }

            if(flag){//flag가 true면 연속해서 문자가 나타남
                answer++;
            }
        }
        System.out.println(answer);
    }
}

 

 

📣 comment

알고리즘을 푸는데 dfs나 재귀 유형을 풀다보니 기본적인 구현문제를 잘 안 풀어서 구현 문제를 최근에 풀기 시작했다. 쉽다고 생각했던 문제가 어려워서 몇 번이나 틀리기도 하고 생각보다 잘 풀려서 기분이 좋기도 하고 그렇다. 

역시 연습만이 답인 것 같다.