[백준] 1316번: 그룹 단어 체커 | C++ 풀이

# 문제

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

 

 

---

 

# 풀이

더 좋은 방법이 있을 것 같은데... 우선 머릿속에 떠오른 방법을 고집해 코드를 완성했다.

이후 다른 분들의 코드 구경 중 공부해두고 싶은 코드를 발견해 링크해두었고, 추가부록처럼 chat GPT가 짠 코드도 덧붙여두니 참고하길 바란다.

우선 내 정답 소스코드부터 확인해보자.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); // 두 표준 입출력 동기화 해제

    int n;
    cin >> n;
    int cnt = 0;

    while (n--) {
        int alphabet[26] = {0};
        bool check = 1;
        string word;
        cin >> word;

        // step 1. 등장하는 알파벳 체크
        for (int i = 0; i < word.length(); i++) {
            alphabet[word[i] - 97]++;
        }

        // step 2. 그룹 단어 검사
        for (int i = 0; i < 26; i++) {

            // 등장횟수 1회까지는 검사하지 않아도 됨
            if (alphabet[i] == 0 || alphabet[i] == 1) continue;

            int first = word.find(i+97); // 첫 번째 등장 위치
            for (int j = 1; j < alphabet[i]; j++) { // 반복 횟수는 등장 횟수-1
                int next = word.find(i+97, first+1); // 다음 등장 위치
                if (next != first+1) {
                	// 등장 위치가 연속되지 않았을 경우
                    check = 0;
                    break;
                }
                first = next; // 밀어내고 다음 체크 진행
            }
            if (!check) break;
        }

        // step 3. 그룹 단어 카운트
        if (check) cnt++;
    }

    cout << cnt;
    return 0;
}

 

문제를 보고 떠올린 방법은 여러번 등장한 알파벳의 등장 인덱스를 차례로 확인하다가 연속되지 않은 인덱스가 등장할 경우 그룹 단어가 아니라고 체크해주는 것이었다. 여기에 점차 덩어리를 붙여 현재의 코드를 완성하였으니 앞부분부터 하나씩 확인해보자.

 

 

 

📌 STEP 1. 등장하는 알파벳 체크

int alphabet[26] = {0};
bool check = 1;
string word;
cin >> word;

// step 1. 등장하는 알파벳 체크
for (int i = 0; i < word.length(); i++) {
    alphabet[word[i] - 97]++;
}

처음엔 알파벳 체크를 안 하고 진행했는데, 이 과정을 따로 해주는 게 더 깔끔해질 것 같아 추가하였다.

STEP 2에서 2번 이상 등장한 알파벳들만 인덱스 체크를 해주기 위해 알파벳들의 등장 횟수를 세어주었다.

그리고 그룹 단어가 아니라면 더이상 검사를 진행할 필요가 없기 때문에 이를 판별할 check 변수를 true로 선언, 아스키 코드값을 활용하여 입력된 단어의 알파벳을 체크해주었다.

 

 

 

📌 STEP 2. 그룹 단어 검사

// step 2. 그룹 단어 검사
for (int i = 0; i < 26; i++) {

	// 등장횟수 1회까지는 검사하지 않아도 됨
    if (alphabet[i] == 0 || alphabet[i] == 1) continue;

    int first = word.find(i+97); // 첫 번째 등장 위치
    for (int j = 1; j < alphabet[i]; j++) { // 반복 횟수는 등장 횟수-1
        int next = word.find(i+97, first+1); // 다음 등장 위치
        if (next != first+1) {
            // 등장 위치가 연속되지 않았을 경우
            check = 0;
            break;
        }
        first = next; // 밀어내고 다음 체크 진행
    }
    if (!check) break;
}

이제는 그룹 단어인지 아닌지 검사할 차례다.

알파벳의 등장 횟수를 배열에 저장해두었기 때문에 2회 이상 등장한 알파벳만 검사를 진행하면 된다. 따라서 등장 횟수 0회 혹은 1회는 continue 처리해 불필요한 검사를 하지 않도록 했다.

 

2회 이상 등장한 단어들은 첫번째 등장 인덱스와 그 다음 등장 인덱스를 비교해주면 된다.

이때 다음 등장 위치는 첫번째 등장 인덱스 이후부터 검사하도록 값을 넣어주었고,  반복 횟수는 2번 등장할 경우 첫번째와 두번째를 검사(1회), 3번 등장할 경우 첫번째와 두번째, 두번째와 세번째를 검사(2회)하면 되니까 등장 횟수 - 1이다.

 

만약 등장 위치가 연속되지 않았을 경우에는 check를 false로 바꾸고 반복문을 두 번 벗어나고, 연속되었을 경우에는 인덱스를 밀어내면 다음 체크를 진행한다.

 

 

 

📌 STEP 3. 그룹 단어 카운트

// step 3. 그룹 단어 카운트
if (check) cnt++;

모든 검사를 마친 후엔 check 값을 확인해 true인 것들만 카운트 해주면 끝!

 

 

 

 

 

---

 

 

좋은 방법이라고 생각한 코드는 아래 링크해둔 글인데, unique와 erase를 활용한 코드다.

C++로 알고리즘을 푸는 것의 가장 큰 장점은 라이브러리에 구현된 다양한 기능이 많다는 것이지 않을까. 그런 장점을 잘 살린 코드라고 생각해 링크해두었다. 공부를 넘어서 적재적소에 잘 떠올려 쓸 수 있도록 나도 더 노력해야지...

백준 1316 그룹 단어 체커 c++ [컴공과고씨]

 

 

 

다음은 좀 더 가독성 좋고 효율적인 코드가 뭘까 고민하다 chat GPT에게 질문을 던졌다.

대답으로 제공된 코드는 아래와 같다. 구체적으로 물어보지 않는 이상 정확도가 떨어지기도 하고... 반쯤 재미로 물어봤던 건데 나보다 나은 것 같다. 알파벳 배열을 활용한 건 비슷한데 얘는 등장하는 알파벳의 횟수를 저장하지 않고 bool 값으로 저장했다. 이 방법이 훨씬 코드도 짧고 이해하기도 쉬운듯 하다. 공부하자 공부... 떠올리는 것도 실력

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

bool isGroupWord(string word) {
    bool visited[26]; // 알파벳의 방문 여부를 저장하기 위한 배열

    // visited 배열 초기화
    memset(visited, false, sizeof(visited));

    for (int i = 0; i < word.length(); i++) {
        // 현재 문자와 이전 문자가 다르다면
        if (i > 0 && word[i] != word[i - 1]) {
            // 이전에 나온 적이 있던 문자인지 확인
            if (visited[word[i] - 'a']) {
                return false; // 그룹 단어가 아님
            }
        }
        visited[word[i] - 'a'] = true; // 문자의 방문 여부를 체크
    }
    return true; // 그룹 단어임
}

int main() {
    int n;
    cin >> n; // 단어의 개수 입력

    int count = 0;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word; // 단어 입력

        if (isGroupWord(word)) {
            count++; // 그룹 단어인 경우 count 증가
        }
    }

    cout << count << endl; // 그룹 단어의 개수 출력

    return 0;
}

 

 

---

 

 

1316번: 그룹 단어 체커