[BOJ] #2941 크로아티아 알파벳

시간 제한	메모리 제한	정답 비율
1 초	128 MB	46.116%

2941번: 크로아티아 알파벳

 

문제

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

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

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

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

 

해결

1. 답으로 출력할 변수 ans를 입력받은 문자열의 길이로 초기화한다.
2. 문자열을 탐색하면서 바로 이전 문자 s[i-1]과, 현재 보고 있는 문자 s[i]를 합하여 tmp라는 문자열을 만든다.
3. 대부분의 경우, tmp가 크로아티아 알파벳에 해당한다면, 전체문자열 길이에서 -1을 해준다.
4. 하지만 알파벳 "dz="를 판단할 때는 -2를 해주어야 하기 때문에 "dz"를 만나면 그 뒤의 문자가 '='인지 판단하여 맞다면 ans에서 2만큼 빼주고, 아니라면 넘어간다.
5. 이렇게 매번 두 개의 문자를 합쳐 하나의 tmp라는 문자열로 만든 다음 문자열 s 길이만큼 탐색하고 나면 마지막에 출력하는 ans가 정답이 된다.

 

코드

메모리	시간
1988 KB	0 ms

#include <iostream>
#include <string>
using namespace std;
int ans;
string s;
int main() {
    cin >> s;
 
    string tmp;
    ans = s.length();
    for (int i = 1; i <= s.length(); i++) {
        tmp += s[i-1]; tmp += s[i];
        if (tmp == "c=" || tmp == "c-" || tmp == "d-" || tmp == "lj" || tmp == "nj" || tmp == "s=" || tmp == "z=") {
            ans -= 1;
        }
        else if (tmp == "dz") {
            if (i + 1 < s.length() && s[i + 1] == '=') {
                ans -= 2;
                i++;
            }
        }
        tmp = "";
    }
    printf("%d", ans);
    return 0;
}

 

후기

새롭게 시작한 알고리즘 스터디의 첫번째 문제가 크로아티아 알파벳이 되었는데 정말 다양한 방식의 풀이가 있어서 너무 흥미로웠고 앞으로도 알고리즘 스터디가 잘 이루어지고 인간적으로도 친해졌으면 하는 바람이다..!

다른 풀이 방법 1

크로아티아 알파벳의 규칙 활용 → '=', '-'

1. 일단 '='과 '-'를 만나면 무조건 전체 길이에서 1 만큼 빼주고,
2. 나머지 기호가 없는 크로아티아 알파벳에 해당하는 'lj', 'nj', 'dz' 이 세가지 경우만 조건문으로 처리해주었다.

다른 풀이 방법 2 - java

string 내장함수 사용 - java로 풀었을 경우.

1. string.contains("크로아티아 알파벳"); 으로 문자열에 알파벳이 있는지 판단 후
2. string.replace("크로아티아 알파벳", "#"); 으로 크로아티아 알파벳을 공백 또는 하나의 문자열로 대체하여
3. 마지막에 전체 길이를 세어 출력했다.

c++로 풀었을 경우 string.find 로 찾을 수 있지만, 반환값이 처음으로 찾은 위치이고, string.replace는 인자로 범위가 필요하기 때문에 c++인 경우 현재처럼 푸는 것이 맘 편할 것 같다.