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

 

처음에 이 문제를 보고 세운 전략은 string 자료형으로 그룹 단어를 받고,

앞 index부터 바로 앞 단어와 글자가 같으면 pass하고, 다르면 앞 index에서 등장한 문자인지를 확인하여 그룹단어 여부를 확인한다.

다만, 이 상황에서 이미 등장한 문자열을 string자료형에 concat을 시키는 방식으로 코드를 구현하였다.

해당하는 방식으로 코드를 구현한 결과는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(void){
    int how_many_repeat;

    cin >> how_many_repeat;

    string checker;
    string non_pass_element;

    int count = 0; // how many group element in this group 

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

        cin >> checker;
        int len_of_string = checker.size(); // input string and check len
        char past_element = checker[0];
        bool final_check = true;

        for(int j = 0; j < len_of_string; j++){ //check all string element
            
            if (j == 0) {
                non_pass_element = checker[j]; // start element setting
            }

            else if(checker[j] != past_element){

                char check_element = checker[j]; // element 
                int len_checker = non_pass_element.size(); // compare values

                bool group_element_check = true; // default boolean flag
                
                for(int k = 0; k < len_checker; k++){ // compare values by iteration

                    if(non_pass_element[k] == check_element){
                        group_element_check = false;
                    } 
                }

                if(group_element_check == false){

                    final_check = false;

                    break; // not group word
                }

                else {
                    non_pass_element += checker[j];
                    past_element = checker[j];
                }
            }

        }

        if (final_check == true) count += 1;

        checker.clear();
        non_pass_element.clear();

    }

    cout << count << "\n";

    return 0;

}

하지만 결과적으로 생각해 볼 때, 이 코드는 계속해서 이전의 인덱스에서 등장한 문자인지를 확인하기 위해서 string을 처음부터 끝까지 계속해서 iteration을 해야하는데 매우 비효율적이라고 할 수 있다.

 

즉, 차라리 앞에 등장한 문자인지를 확인하는 목적으로 각 문자의 utf-8코드에 맞게끔 초기화 값이 0인 배열을 하나 파고, 문자가 등장할 경우에 그 숫자를 1 증가시킨다. 그러면 체크하는 과정에서 해당 배열의 값이 1이면 그룹단어가 아니라는 것을 쉽게 파악할 수 있다.

 

또한, 이 방식으로 하면 boolean flag를 최종적으로 그룹 단어 여부를 한번만 확인하면 되어서 논리적으로도 훨씬 간단하게 코드를 짤 수 있다. (Boolean flag의 경우에는 매우 유용하므로 잘 알아두도록 하자)

 

해당하는 방식으로 코드를 짜면 다음과 같다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(void){

    int repeat_value;
    cin >> repeat_value;
    int group_string_count = 0; // count group string

    for (int i = 0; i < repeat_value; i++){
        string check_string;
        cin >> check_string; // input string
        bool if_string_group = true;
        
        int alphabet[123] = {0}; // Initial setting (alphabet count)
        int len_string = check_string.size();
        char before_char = '0';

        for (int j = 0; j < len_string; j++){
            
            int check_char = check_string[j];
            if (check_char == before_char){
                continue;
            }
            else{
                if (alphabet[check_char] == 0){
                    alphabet[check_char] += 1;
                }
                else{
                    if_string_group = false;
                    break;
                }

                before_char = check_char; // Reinitialize before_char
            }

        }

        if (if_string_group == true) group_string_count += 1;
    }

    cout << group_string_count << "\n";
    return 0;

}

 

자료의 데이터값과 배열의 index값을 맞추어 손쉽게 계산하는 방법은 매우 자주 사용하는 방법중에 하나이므로

이 방식을 잘 정리해두어야 한다.

 

특히 ASCII와 결합하여 정리할 때 매우 좋은 방법중에 하나이다.