BOJ 2941 - 크로아티아 알파벳

문제 링크

문제#

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

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

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

입력#

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

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

출력#

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

풀이#

문자열을 한 글자씩 보되, 몇몇 조합은 한 글자로 취급해야 한다. 그래서 현재 위치에서 두 글자나 세 글자를 함께 봐야 하는 경우를 먼저 확인하고, 맞으면 그만큼 건너뛰는 방식으로 세면 된다.

특히 dz=는 세 글자짜리 예외라서 다른 두 글자 패턴보다 먼저 처리해야 한다. 그 순서가 꼬이면 d와 z=를 따로 세어 버리는 실수가 생긴다.

결국 이 문제는 특수 패턴의 우선순위를 잘 정해 두고 문자열 인덱스를 이동시키는 구현 문제다. 패턴 목록만 정확히 반영하면 코드 자체는 길지 않다.

코드#

#include <iostream>
using namespace std;
 
int len;
string s;
 
void input() {
	cin >> s; 
} 
 
void solve() {
	len = s.length();
 
	for (int i = s.length() - 1; i >= 0; i--) {
		switch(s[i]) {
		case '=':
			if(s[i - 1] == 'c' || s[i - 1] == 's') {
				len--;
				i--;
			}
			else if(s[i - 1] == 'z') {
				if(s[i - 2] == 'd') {
					len = len - 2;
					i = i - 2;
				}
				else {
					len--;
					i--;
				}
			}
			break;
 
		case '-':
			if(s[i - 1] == 'c' || s[i - 1] == 'd') {
				len--;
				i--;
			}
			break;
 
		case 'j':
			if(s[i - 1] == 'l' || s[i - 1] == 'n') {
				len--;
				i--;
			}
			break;
 
		default:
			break;
		}
	}
 
	cout << len << '\n';
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	input();
 
	solve();
 
    return 0;
}

복잡도#

• 시간 복잡도: 문자열을 왼쪽부터 한 번 훑으며 크로아티아 알파벳을 판정하므로 $O(L)$이다.
• 공간 복잡도: 입력 문자열 외에는 상수 개수의 변수만 사용하므로 $O(1)$이다.

마무리#

두 글자와 세 글자 특수 패턴을 먼저 소비하면 크로아티아 알파벳 개수는 흔들리지 않는다.