문자열 delimiter 분해 - strpbrk & 맞왜틀 (BOJ 2941 크로아티아 알파벳)

특정 문자의 조합을 하나의 크로아티아 알파벳으로 카운트하라는 문제.

'특정 문자'를 delimiter로 잡고, 문자열을 분해하면 되겠다고 생각함.

Delimiter가 여러개인데 (=, -, j), 메뉴얼에서만 잠깐 봤던 'strpbrk' 함수를 활용해서, 여러 개 delimiter 한번에 처리 가능.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    char line[101]; // ◀ 문제점1
    fgets(line, sizeof(line), stdin); // ◀ 문제점2
    const char* sep = "-=j";
    char *str = line;
    char *prev = line;
    
    int cnt = 0;
    do{
        str = strpbrk(str, sep);
        
        if (!str) { // null
            cnt += strlen(prev);
            break;
        }
        
        cnt += str - prev; // Token 제외 글자 수
        if (*str == '=') {
            //cnt -= 1; // c=, s=, z= (이미 =가 카운트 안됬으므로, 저 둘이 합쳐서 한글자로 카운트됨)
			// ◀ 문제점3
                        
            if (*(str - 1) == 'z' && str - 2 >= prev && *(str - 2) == 'd')
                cnt -= 1; // case 'dz='            
        }
        else if (*str == '-') {
            //cnt -= 1; // 'c-' or 'd-' // ◀ 문제점3
        }
        else if (*str == 'j') {
            if (str - 1 >= prev && (*(str - 1) == 'l' || *(str - 1) == 'n')){
                //cnt -= 1; // 'lj' or 'nj'
            }
            else{
                cnt += 1; // 'j' is single character; make it count
            }
        }

        str++;
        prev = str;
    } while (str);

    cout << cnt;   
	return 0;
}

단점) C-style string으로 처리해야해서 좀 복잡해질 수 있음. 특히, Delimiter의 위치를 찾아주기 때문에, delimiter 앞에 있었던 문자들을 다루려면 포인터 써야함 (str-1, str-2 같이).

 

처음 코드를 짜고 3가지 문제점을 발견했음.

 

문제점 1

문제 이해의 영역인데, 100글자 인풋이 '크로아티아 알파벳' 글자로 이루어졌으면?

char array 크기 101만 가지고는 다 못 읽지~ 최대 301 은 있어야 안전 (널 문자 읽는거 포함)

 

문제점 2 (맞왜틀)

fgets로 문자열을 입력받으면, 엔터 칠때 맨 뒤에 추가되는 개행문자 '\n' 도 읽어들임.

파일에서 직접 문자 입력받아서 테스트할땐 몰랐는데, 직접 손으로 입력할때서야 알아서 맞왜틀? 함.

 

해결 방법 :

    line[strcspn(line, "\n")] = 0; // ★ fgets takes '\n' as input too; trimming needed
    // https://stackoverflow.com/questions/2693776/removing-trailing-newline-character-from-fgets-input

아니면, std::string을 쓴다.

 

문제점 3

저러면, =나 - 만 입력받으면 틀림.

또, a= 혹은 a- 같이 invalid croatian alphabet이 와도 한 개의 문자로 치게 됨.

그러나, 문제에서 '크로아티아 문자'만 입력한다고 했으니, 위의 경우는 없을 듯 하지만, 일단 틀려서 모든 가능성을 열어두기로 함. 

 

 

요런 문제점들을 하나씩 파악해서 고쳤더니 통과했음 (몇 시간 날림)

#include <bits/stdc++.h>
#define READY_CYCLE() str++; prev = str;

using namespace std;

int main() {
    char line[301]=""; // ◀ 문제점1 Fix
    fgets(line, sizeof(line), stdin); // ◀ 문제점2 Fix
    line[strcspn(line, "\n")] = 0; // fgets takes '\n' as input too; trimming needed
    const char* sep = "-=j";
    char *str = line;
    char *prev = line;
    
    int cnt = 0;
    char suffix;
    do{
        str = strpbrk(str, sep);
        
        if (!str) { // null
            cnt += strlen(prev);
            break;
        }
        
        cnt += str - prev; // Token 제외 글자 수
        if (*str == '=') {
            //cnt -= 1; // c=, s=, z= (이미 =가 카운트 안됬으므로, 저 둘이 합쳐서 한글자로 카운트됨)

            // only '=' // ◀ 문제점3 Fix
            if (str - 1 < prev){
                cnt += 1;
                READY_CYCLE()
                continue;
            }
            
            suffix = *(str - 1);
            if (!((suffix = *(str-1)) == 'c' || suffix == 's' || suffix == 'z')) // ◀ 문제점3 Fix
                cnt += 1;
            else if (suffix == 'z' && str - 2 >= prev && *(str - 2) == 'd') // strcmp(str-2,"dz=")
                cnt -= 1; // case 'dz='            
        }
        else if (*str == '-') {
            //cnt -= 1; // 'c-' or 'd-'

            // only '-' // ◀ 문제점3 Fix
            if (str -1 < prev) {
                cnt += 1;
                READY_CYCLE()
                continue;
            }

            suffix = *(str - 1);
            if (!(suffix == 'c' || suffix == 'd')) // ◀ 문제점3 Fix
                cnt += 1;
        }
        else if (*str == 'j') {
            if (str - 1 >= prev && (*(str - 1) == 'l' || *(str - 1) == 'n')){
                //cnt -= 1; // 'lj' or 'nj'
            }
            else{
                cnt += 1; // 'j' is single character; make it count
            }
        }

        READY_CYCLE()
    } while (str);

    cout << cnt;   
	return 0;
}

 

코드를 보면, 난잡하고 이해하기 힘듬.

Delimiter 기준으로 앞글자(str-1), 앞앞글자(str-2)를 모두 if문을 중첩해서 체크하기 때문.

그래서, std::string을 쓰고, strcmp와 strncpy 조합으로 크로아티아 문자를 한꺼번에 비교하는 코드로 개량함.

#include <bits/stdc++.h>
#define READY_CYCLE() str++; prev = str; // do-while 루프 마지막에서, delimiter를 가리키던 str를 한칸 앞으로 옮겨주고, prev 갱신해줌. 새 루프 준비하는 함수.

using namespace std;

int main() {
    string line;
    getline(cin, line); // ◀ No more fgets!
    const char* sep = "-=j";
    char *str = &line[0];
    char *prev = &line[0];

    int cnt = 0;
    char dest[3] = {0, 0, 0}; // for strncpy
    			// 앞 두 캐릭터만 쓸 것 (3번째는 null문자로만 써서 Null-term string 구현)
    do{
        str = strpbrk(str, sep);

        // Null; no more delimiters found
        if (!str) {
            cnt += strlen(prev);
            break;
        }

        cnt += str - prev; // Token 제외 글자 수
        if (*str == '=') {
            if (str - 2 >= prev && strcmp(strncpy(dest, str-2, 2), "dz") == 0) // ★ strncpy로 '=' 바로 이전 2 캐릭터만 복사해서 비교; 물론 str-2 이 valid 할때만
                cnt -= 1; // case 'dz='
        }
        else if (*str == '-') {
            // Nothing to be done here (Token already not counted)
        }
        else if (*str == 'j') {
            // ★ strncpy로 'j' 포함 이전 캐릭터 함께 복사해서 비교; str-1 이 valid 할때만
            if (!(str - 1 >= prev && (strcmp(strncpy(dest, str - 1, 2), "lj") == 0 || strcmp(strncpy(dest, str - 1, 2), "nj") == 0))) {
                cnt += 1; // 'j' is single character; make it count
            }
        }

        READY_CYCLE()
    } while (str);

    cout << cnt;
	return 0;
}

훨씬 깔끔해졌다! 이정도면 만족 :)

 

 

공부 할 부분 1) std::string split (알고리즘 노트 string.cpp) 개량해서, 여러 delimiter 받을 수 있게 해보자.

 

공부 2) strspn (strcspn) 도 재밌어보인다. 활용도 높을 듯. 알아두자. (문제점 2 해결할때 실제로 씀)