[BOJ-2941][C++] 크로아티아 알파벳

문제

예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다.

크로아티아 알파벳	변경
č	c=
ć	c-
dž	dz=
đ	d-
lj	lj
nj	nj
š	s=
ž	z=

 

예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.

dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다. lj와 nj도 마찬가지이다. 위 목록에 없는 알파벳은 한 글자씩 센다.

 

입력

첫째 줄에 최대 100글자의 단어가 주어진다. 알파벳 소문자와 '-', '='로만 이루어져 있다.

단어는 크로아티아 알파벳으로 이루어져 있다. 문제 설명의 표에 나와있는 알파벳은 변경된 형태로 입력된다.

 

출력

입력으로 주어진 단어가 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.

 

예제 입력 1

ljes=njak

 

예제 출력 1 

6

 

예제 입력 2 

ddz=z=

 

예제 출력 2 

3

 

예제 입력 3 

nljj

 

예제 출력 3 

3

 

예제 입력 4 

c=c=

 

예제 출력 4 

2

 

예제 입력 5 

dz=ak

 

예제 출력 5 

3

 

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #5 1번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: cake_monotone, evenharder, handong, jh05013, veydpz, zzangho
• 문제의 오타를 찾은 사람: jh05013
• 어색한 표현을 찾은 사람: jh05013

 

알고리즘 분류

• 구현
• 문자열

 

 

문제 출처

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

2941번: 크로아티아 알파벳

 

---

 

문제 해결 방법

문제의 도표에 제시된 크로아티아 알파벳을 '특수한 크로아티아 알파벳' 이라고 하자.

단어를 입력 받은 후, 단어의 크기 만큼의 bool 형 배열(flag)을 동적 할당하여 생성한 후, 1로 초기화 한다. 그 다음, 단어의 마지막 부분(word.length()) 인덱스 부터 단어의 첫 번째 인덱스까지 순회하면서 특수한 크로아티아 알파벳을 체크한다. (특수한 크로아티아 알파벳인 경우, 해당 위치의 bool형 배열의 값을 0으로 초기화 한 후, 개수를 나타내는 변수(count)의 크기를 1씩 증가시킨다.)

 

최종적으로 flag 배열에서 특수한 크로아티아 알파벳을 제외한 부분만 1로 남게 되는데, 1로 남은 부분의 총 개수를 count 변수에 더해 주고, count 값을 출력해준다.

 

예를 들면 다음과 같다.

 

<단계 0>

count : 0

입력 받은 문자열 배열 : word

l

j

e

s

=

n

j

a

k

 ◀ 문자열의 끝 인덱스에서 처음 인덱스로 순회를 하면서 특수한 크로아티아 알파벳을 찾는다.

 

입력 받은 문자열 배열의 크기와 비슷한, 1로 채워진 배열 : flag

1

1

1

1

1

1

1

1

1

 

<단계 1>

count : 1

입력 받은 문자열 배열 : word

l

j

e

s

=

n

j

a

k

 ◀ 문자열의 끝 인덱스에서 처음 인덱스로 순회를 하면서 특수한 크로아티아 알파벳을 찾는다.

 

입력 받은 문자열 배열의 크기와 비슷한, 1로 채워진 배열 : flag

1

1

1

1

1

0

0

1

1

 

 

<단계 2>

count : 2

입력 받은 문자열 배열 : word

l

j

e

s

=

n

j

a

k

 ◀ 문자열의 끝 인덱스에서 처음 인덱스로 순회를 하면서 특수한 크로아티아 알파벳을 찾는다.

 

입력 받은 문자열 배열의 크기와 비슷한, 1로 채워진 배열 : flag

1

1

1

0

0

0

0

1

1

 

<단계 3>

count : 3

입력 받은 문자열 배열 : word

l

j

e

s

=

n

j

a

k

 ◀ 문자열의 끝 인덱스에서 처음 인덱스로 순회를 하면서 특수한 크로아티아 알파벳을 찾는다.

 

입력 받은 문자열 배열의 크기와 비슷한, 1로 채워진 배열 : flag

0

0

1

0

0

0

0

1

1

 

<단계 4>

count : 6 (3 + 3)

입력 받은 문자열 배열 : word

l

j

e

s

=

n

j

a

k

 

입력 받은 문자열 배열의 크기와 비슷한, 1로 채워진 배열 : flag

0

0

1

0

0

0

0

1

1

문자열의 처음 인덱스부터 끝 인덱스로 순회를 하면서 값이 1일 경우 count의 값을 하나씩 증가시켜준다. ▶

 

 

※ 특수한 크로아티아 알파벳 중, dž(dz=), ž(z=) 알파벳은 dž(dz=) 먼저 처리해 준 후, z= 를 처리해주도록 한다.

코드

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    string word;
    int count;

    getline(cin, word);

    bool *flag = new bool[word.length()];
    memset(flag, 1, word.length());

    // Croatian Alphabet
    // - č <=> c=     - ć <=> c-
    // - dž <=> dz=   - đ <=> d-
    // - lj <=> lj    - nj <=> nj
    // - š <=> s=     - ž <=> z=
    
    count = 0;
    for (int i = word.length(); i > 0; i--) {
        if (word[i] != 0) {
            //  Check { c=, dz=, s=, z= }
            if (word[i] == '=') {
                if ((word[i - 1] == 'c') || (word[i - 1] == 's')) {
                    count++;
                    flag[i] = 0;
                    flag[i - 1] = 0;
                }
                else if (word[i - 1] == 'z') {
                    if (word[i - 2] == 'd') {
                        count++;
                        flag[i] = 0;
                        flag[i - 1] = 0;
                        flag[i - 2] = 0;
                    }
                    else {
                        count++;
                        flag[i] = 0;
                        flag[i - 1] = 0;
                    }
                }
            }
            // Check { c-, d- }
            else if (word[i] == '-') {
                if ((word[i - 1] == 'c') || (word[i - 1] == 'd')) {
                    count++;
                    flag[i] = 0;
                    flag[i - 1] = 0;
                }
            }
            // Check { lj, nj }
            else if (word[i] == 'j') {
                if ((word[i - 1] == 'l') || (word[i - 1] == 'n')) {
                    count++;
                    flag[i] = 0;
                    flag[i - 1] = 0;
                }
            }
        }
    }

    for (int i = 0; i < word.length(); i++) {
        if (flag[i] == 1) {
            count++;
        }
    }

    cout << count << endl;

    delete(flag);

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [문자열]