[C] 백준/2941번 write-up

 

사실 브론즈 문제들도 write-up 작성을 하고싶지만, 개인적으로 난이도가 너무 낮아 의미가 없을 것 같아서 실버 이상으로 풀이만 하고있습니다.

 

풀이할 문제는 2018년도 월드컵 준우승을 한 크로아티아 알파벳을 구하는 문제입니다.

 

간단한 문자처리만 하는 문제입니다.

 

문제 풀기 전에 잠깐 로직을 구상해볼까요?

 

1. 주어지는 문자열은 100글자의 소문자 알파벳과 =, -으로만 주어진다는 점으로 미루어보아, 간단한 문자열 처리도 하기 힘든(?) 우리의 C언어님은 입력받은 문자열을 일일이 전수조사를 해야될 것 같습니다.

 

2. 그렇다면 과연 입력받은 문자열에 변환을 해주어야할 크로아티아 문자가 몇개나 있을까요? 답은 '알 수 없다' 입니다.

그런 관계로, 크로아티아 문자열 한 개를 찾을때 마다 문자열을 전수조사 해주어야 합니다.

그러면 시간복잡도는 O(N^2) 가 되겠네요.

 

3. C언어에서 배열은 배열 변수 그 자체로 보지않고, 해당 배열변수는 메모리에 적재된 공간의 첫 번째 메모리 주소를 가르킵니다.

즉, 문자열 전체를 한번에 비교하기가 불가능하다는 뜻이기도 하고, MZ 세대에 어울리지 않는 그런 엄청난 언어이기도 합니다.

 

로직 구상이 끝났으니 코딩을 해볼까요?

 

#include <stdio.h>
#include <string.h>

int main() {

    int len;
    int cnt = 0;
    char str[101];

    scanf("%s", str);

    len = strlen(str);

    for(int i = 0; i < len/2; ++i) {
        for(int j = 0; j < len; ++j) {
            if (str[j] == 'c' && str[j + 1] == '=') {
                str[j] = ' ';
                str[j + 1] = ' ';
                cnt++;
            }
            if (str[j] == 'c' && str[j + 1] == '-') {
                str[j] = ' ';
                str[j + 1] = ' ';
                cnt++;
            }
            if (str[j] == 'd' && str[j + 1] == 'z' && str[j + 2] == '=') {
                str[j] = ' ';
                str[j + 1] = ' ';
                str[j + 2] = ' ';
                cnt++;
            }
            if (str[j] == 'd' && str[j + 1] == '-') {
                str[j] = ' ';
                str[j + 1] = ' ';
                cnt++;
            }
            if (str[j] == 'l' && str[j + 1] == 'j') {
                str[j] = ' ';
                str[j + 1] = ' ';
                cnt++;
            }
            if (str[j] == 'n' && str[j + 1] == 'j') {
                str[j] = ' ';
                str[j + 1] = ' ';
                cnt++;
            }
            if (str[j] == 's' && str[j + 1] == '=') {
                str[j] = ' ';
                str[j + 1] = ' ';
                cnt++;
            }
            if (str[j] == 'z' && str[j + 1] == '=') {
                str[j] = ' ';
                str[j + 1] = ' ';
                cnt++;
            }
        }
    }
    for(int i = 0; i < len; ++i){
        if(str[i] != ' ') {
            cnt++;
        }
    }
    printf("%d", cnt);
}

 

조건문에서 일일히 문자열 처리를 해주었습니다.

 

사실 위와 같이 코드를 작성하면, 메모리 낭비도 심할뿐더러 가독성 또한 안좋아지게 됩니다만

 

실버 5 문제에서 그정도 고민까지는 안해도 될 것 같네요.

 

그리고 전수조사를 위해 문자열 1개 당 한번의 전수조사를 하도록 작성하였습니다.

 

그리고 조금이라도 낭비를 줄이고싶어서 첫 번째 for 문에서는 0 ~ len/2 까지만 루프를 돌게 하였는데요

 

크로아티아 문자를 보면 최소 문자열의 길이가 2개 인것을 볼 수 있습니다.

 

즉, 모든 문자열이 전부 치환해야 될 크로아티아 문자로만 구성이 될 경우, 최대로 루프를 돌아야되는 횟수는 len / 2 회 라는 것이죠.

 

이문제의 핵심 로직이 아닐까 싶습니다.